#include <fstream> // varianta cu stream-uri
#include <vector>
#include <queue>
#define DIM 50002
#define INF 10000

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

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

void read() {
     
     fin>> n>> m;
     for ( ; m-- ; ) {
         fin>> x>> y>> c;
         G[x].push_back(y);
         Cost[x].push_back(c);
         }
}
void solve() {
     
     memset ( visited, INF, sizeof(visited) );
     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]-1;
         if ( x >= INF ) fout<<0<<" ";
         else fout<<x<<" ";
         }
}
      
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 :)