#include <cstdio>
#include <vector>
#include <queue>
#define DIM 50002

using namespace std;

vector <int> G[DIM], Cost[DIM];
queue <int> Q;
int n, m, x, y, c, i, visited[DIM];

void read() {
     
     scanf ("%d%d\n", &n, &m);
     for ( ; m-- ; ) {
         scanf ("%d%d%d", &x, &y, &c);
         G[x].push_back(y);
         Cost[x].push_back(c);
         }
}
void solve() {
     
     Q.push(1);
     visited[1]=1;
     while ( Q.size () ) {
           x = Q.front();
           Q.pop();
           for (i = 0; i < G[x].size(); ++i) {
               if (Cost[x][i] + visited[x] < visited [ G[x][i] ])
                    visited[ G[x][i] ] = Cost[x][i] + visited[x];
               if ( ! visited [ G[x][i] ] ) {
                    visited[ G[x][i] ] = Cost[x][i]+visited[x];
                    Q.push ( G[x][i] );
                    }
               }
           }
     for (i = 2; i <= n; ++i) {
         x=visited[i]-1;
         if ( x < 0 ) printf ("0 ");
         else printf ("%d ",x);
         }
}
      
int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    read();
    solve();
    return 0;
}