#include<fstream>
#include<vector>
#include<queue>

using namespace std;

#define Nmax 50001

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector<pair<int, int> > G[Nmax];
int N, M, D[Nmax], frecv[Nmax];
bool ok;

void bellmanford() {
     
     vector<pair<int, int> >:: iterator it;
     queue<int> Q;
     int nod;
     
     fill(D+1, D+N+1, 1<<30);
     Q.push(1);
     D[1] = 0;
     frecv[1] = 1;
     while(!Q.empty()) {
                       nod = Q.front();
                       Q.pop();
                       for(it = G[nod].begin(); it!=G[nod].end(); ++it) 
                              if(D[it->first] > D[nod] + it->second) {
                                              D[it->first] = D[nod] + it->second;
                                              Q.push(it->first);
                                              frecv[it->first]++;
                                              /*if(frecv[it->first] >= N) {
                                                                  g<<"Ciclu negativ!"<<"\n";
                                                                  f.close(); g.close();
                                                                  ok = false;
                                                                  return;
                                              }*/
                              }
     }
}                  

int main() {
    
    int i, x, y, z;
    
    f>>N>>M;
    while(M--) {
               f>>x>>y>>z;
               G[x].push_back(make_pair(y,z));
    }
    
    ok = true;
    bellmanford();
    
    //if(ok) {
           for(i=2; i<=N; ++i)
                    g<<D[i]<<" ";
           g<<"\n";
    
           f.close();
           g.close();
    //}
    
    return 0;
}