#include <cstring>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 const int maxm = ;

 const int INF = 0x3f3f3f3f;

 int n, m;

 struct ee {

     int to;

     int nxt;

     int w;

 } edge[maxm];

 int head[maxn], tol;

 void init() {

     memset(head, -, sizeof head );

     tol = ;

 }

 void add(int u, int v, int w) {

     edge[tol].to = v;

     edge[tol].w = w;

     edge[tol].nxt = head[u];

     head[u] = tol++;

 }

 int d1[maxn], d2[maxn];

 bool vis[maxn];

 void spfa(int s, int t, int d[]) {

     for(int i=; i<n; ++i) d[i] = INF;

     memset(vis, false, sizeof vis );

     queue<int> q;

     q.push(s);

     d[s] = ;

     vis[s] = true;

     while(!q.empty()) {

         int u = q.front();

         q.pop();

         vis[u] = false;

         for(int i=head[u]; ~i; i=edge[i].nxt) {

             int &v = edge[i].to;

             int &cost = edge[i].w;

             if(d[v] > d[u] + cost) {

                 d[v] = d[u] + cost;

                 if(!vis[v]) {

                     vis[v] = true;

                     q.push(v);

                 }

             }

         }

     }

 }

 void solve() {

     int s = , t = n-;

     spfa(s, t, d1);

     spfa(t, s, d2);

     ll ans = ;

     int minn = d1[t];

     for(int u=; u<n; u++) {

         for(int i=head[u]; ~i; i=edge[i].nxt) {

             int &v=edge[i].to;

             int &cost=edge[i].w;

             if(d1[u]+d2[v]+cost==minn) {

                 ans+=cost;

             }

         }

     }

     printf("%I64d\n", ans*);

 }

 int main() {

     int u, v, l;

     while(~scanf("%d%d", &n, &m)) {

         init();

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

             scanf("%d%d%d", &u, &v, &l);

             add(u, v, l);

             add(v, u, l);

         }

         solve();

     }

     return ;

 }