#include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #define maxn 2000090

 using namespace std;

 typedef long long ll; 

 int n,m,tot;

 int head[maxn],vis[maxn],hea[maxn];

 ll ans,dis[maxn],d[maxn];

 struct node{

     int to,next;

     int val;

 }edge[maxn],edg[maxn];

 void add(int x,int y,int z)

 {

     edge[++tot].to=y;

     edge[tot].next=head[x];

     head[x]=tot;

     edge[tot].val=z;

 }

 void add_nega(int x,int y,int z)

 {

     edg[++tot].to=y;

     edg[tot].next=hea[x];

     hea[x]=tot;

     edg[tot].val=z;

 }

 void dijkstra()

 {

     priority_queue<pair<int,int> >q;

     memset(dis,,sizeof(dis));

     q.push(make_pair(,));dis[]=;

     while(!q.empty())

     {

         int u=q.top().second;q.pop();

         if(vis[u]) continue;

         vis[u]=;

         for(int i=head[u];i;i=edge[i].next)

         {

             int v=edge[i].to;

             if(dis[v]>dis[u]+edge[i].val)

             {

                 dis[v]=dis[u]+edge[i].val;

                 if(!vis[v]) q.push(make_pair(-dis[v],v));

             }

         }

     }

 }

 void dijk()

 {

     priority_queue<pair<int,int> >q;

     memset(d,,sizeof(d));

     memset(vis,,sizeof(vis));

     q.push(make_pair(,));d[]=;

     while(!q.empty())

     {

         int u=q.top().second;q.pop();

         if(vis[u]) continue;

         vis[u]=;

         for(int i=hea[u];i;i=edg[i].next)

         {

             int v=edg[i].to;

             if(d[v]>d[u]+edg[i].val)

             {

                 d[v]=d[u]+edg[i].val;

                 if(!vis[v]) q.push(make_pair(-d[v],v));

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         int x=,y=,z=;

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);add_nega(y,x,z);

     }

     dijkstra();

     dijk();

     for(int i=;i<=n;i++)

         ans+=dis[i]+d[i]/*,printf("%d\n",dis[i])*/;

     printf("%lld",ans);

     return ;

 }