#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

const int INF=0x7FFFFFFF;

const int maxn=+;

const int Maxn=+;

int N,M;

int U[Maxn],V[Maxn],C[Maxn];

struct edge

{

    int from,to,cost;

}e[Maxn];

vector<int>G[maxn];

int dis1[maxn],flag1[maxn];

int dis2[maxn],flag2[maxn];

void init()

{

    for(int i=;i<maxn;i++) G[i].clear();

}

void spfa()

{

    queue<int>Q;

    for(int i=;i<maxn;i++) dis1[i]=INF;

    dis1[]=;

    flag1[]=;

    Q.push();

    while(!Q.empty())

    {

        int h=Q.front();Q.pop(); flag1[h]=;

        for(int i=;i<G[h].size();i++)

        {

            int id=G[h][i];

            if(e[id].from==h)

            {

                if(dis1[h]+e[id].cost<dis1[e[id].to])

                {

                    dis1[e[id].to]=dis1[h]+e[id].cost;

                    if(flag1[e[id].to]==)

                    {

                        flag1[e[id].to]=;

                        Q.push(e[id].to);

                    }

                }

            }

            else if(e[id].to==h)

            {

                if(dis1[h]+e[id].cost<dis1[e[id].from])

                {

                    dis1[e[id].from]=dis1[h]+e[id].cost;

                    if(flag1[e[id].from]==)

                    {

                        flag1[e[id].from]=;

                        Q.push(e[id].from);

                    }

                }

            }

        }

    }

}

void SPFA()

{

    queue<int>Q;

    for(int i=;i<maxn;i++) dis2[i]=INF;

    dis2[N-]=;

    flag2[N-]=;

    Q.push(N-);

    while(!Q.empty())

    {

        int h=Q.front();Q.pop(); flag2[h]=;

        for(int i=;i<G[h].size();i++)

        {

            int id=G[h][i];

            if(e[id].from==h)

            {

                if(dis2[h]+e[id].cost<dis2[e[id].to])

                {

                    dis2[e[id].to]=dis2[h]+e[id].cost;

                    if(flag2[e[id].to]==)

                    {

                        flag2[e[id].to]=;

                        Q.push(e[id].to);

                    }

                }

            }

            else if(e[id].to==h)

            {

                if(dis2[h]+e[id].cost<dis2[e[id].from])

                {

                    dis2[e[id].from]=dis2[h]+e[id].cost;

                    if(flag2[e[id].from]==)

                    {

                        flag2[e[id].from]=;

                        Q.push(e[id].from);

                    }

                }

            }

        }

    }

}

int main()

{

    while(~scanf("%d%d",&N,&M)){

    init();

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

    {

        scanf("%d%d%d",&U[i],&V[i],&C[i]);

        e[i].from=U[i];

        e[i].to=V[i];

        e[i].cost=C[i];

        G[U[i]].push_back(i);

        G[V[i]].push_back(i);

    }

    spfa();

    SPFA();

    int ans=;

    int Len=dis1[N-];

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

    {

        if(dis1[U[i]]+dis2[V[i]]+C[i]==Len||dis2[U[i]]+dis1[V[i]]+C[i]==Len)

            ans=ans+C[i]+C[i];

    }

    printf("%d\n",ans);

    }

    return ;

}