#include <fstream>
#include <vector> // se pare ca tot trebuie sa parsez :(
// daca nu iau 100 nici cu coada implementata static....
#define DIM 500005 // Tai problema ! :))
#define INFI 0x3f3f3f3f
#define DIM2 1<<4
#define CoadaMax 1<<20
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <int> G[DIM], Cost[DIM];
int n, c[CoadaMax];
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 i, x, visited[DIM], p, u;
     for (i=2; i<=n; i++) visited[i]=INFI;
     p = u = 0;
     c[u] = 1;
     visited[1] = 1;          
     while ( p <= u ) {
           x = c[ p++ ];
           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];
                    c[ ++u ] = G[x][i];
                   }
               }
           }
     for (i = 2; i <= n; ++i) {
         
         if ( visited[i] == INFI ) fout<<0<<" ";
         else fout<<visited[i]-1<<" ";
         }
}
      
int main()
{
    freopen ("dijkstra.in","r",stdin);
    read();
    solve();
    return 0;
}
// See'ya next time with a harder problem solved :)
//pe bune ca m-a enervat problema asta