#include <cstdio> 
#include <vector> // se pare ca tot trebuie sa parsez :(
#include <queue>
#define DIM 1<<16
#define INFI 0x3f3f3f3f
#define DIM2 1<<5
using namespace std;

vector <int> G[DIM], Cost[DIM];
queue <int> Q;
int n;
char vec[DIM2];
int poz;
void citeste(int &x)   
{   
  x=0;   
  while(vec[poz]<'0' || vec[poz]>'9')   
       if(++poz==DIM2) fread(vec,1,DIM2,stdin),poz=0;   
  
    while(vec[poz]>='0' && vec[poz]<='9')   
    {   
        x=x*10+vec[poz]-'0';   
        if(++poz==DIM2) fread(vec, 1, DIM2, stdin),poz=0;   
    }   
}   
void read() {
     
     int x, y, c, m;
     citeste (n); citeste (m);
     for ( ; m-- ; ) {
         citeste (x); citeste (y); citeste (c);
         G[x].push_back(y);
         Cost[x].push_back(c);
         }
}
void solve() {
     
     int x,i, visited[DIM];
     for (i=2; i<=n; i++) visited[i]=INFI;
     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];
                    Q.push ( G[x][i] );
                   }
               }
           }
     for (i = 2; i <= n; ++i) {
         x=visited[i];
         if ( x == INFI ) printf("0 ");
         else printf("%d ",x-1);
         }
}
      
int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    read();
    solve();
    return 0;
}
// See'ya next time with a harder problem solved :)