#include <bits/stdc++.h>
using namespace std;
int head[300005];
int n, m, cnt;
struct node
{
    int to, next, vi;
    int from;
} e[300005];

struct heap
{
    int l, id;
    bool operator<(const heap& a)const
    {
        return l > a.l;
    }
};
int dis1[30005];
int dis2[30005];
bool vis[30005];
int u[300005], v[300005], w[300005];

void dijkstra1(int src)
{
    priority_queue<struct heap> q;
    memset(vis, 0, sizeof(vis));
    memset(dis1, 127, sizeof(dis1));
    dis1[src] = 0;
    q.push((heap)
    {
        dis1[src], src
    });
    while(!q.empty())
    {
        heap uu = q.top();
        q.pop();
        int x = uu.id;
        if(vis[x])continue;
        vis[x] = 1;
        for(int i = head[x]; i; i = e[i].next)
        {
            int v = e[i].to;
            if(dis1[v] > dis1[x] + e[i].vi)
            {
                dis1[v] = dis1[x] + e[i].vi;
                q.push((heap{dis1[v], v}));
            }
        }
    }
}
void dijkstra2(int src)
{
    priority_queue<struct heap> q;
    memset(vis, 0, sizeof(vis));
    memset(dis2, 127, sizeof(dis2));
    dis2[src] = 0;
    q.push((heap)
    {
        dis2[src], src
    });
    while(!q.empty())
    {
        heap uu = q.top();
        q.pop();
        int x = uu.id;
        if(vis[x])continue;
        vis[x] = 1;
        for(int i = head[x]; i; i = e[i].next)
        {
            int v = e[i].to;
            if(dis2[v] > dis2[x] + e[i].vi)
            {
                dis2[v] = dis2[x] + e[i].vi;
                q.push((heap{dis2[v], v}));
            }
        }
    }
}

inline void ins(int u,  int v, int w)
{
    e[++cnt].to = v;
    e[cnt].from = u;
    e[cnt].next = head[u];
    e[cnt].vi = w;
    head[u] = cnt;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        u[i]++;
        v[i]++;
        
        ins(u[i], v[i], w[i]);
        ins(v[i], u[i], w[i]);
    }

    dijkstra1(1);
    dijkstra2(n);

    int l = dis1[n];
    long long ans = 0;

    for(int i = 0; i <m; ++i)
    {
        if(dis1[u[i]] + dis2[v[i]] + w[i] == l || dis1[v[i]] + dis2[u[i]] + w[i] == l)
            ans += w[i];
    }
    printf("%lld\n", ans*2);

    return 0;
}
