#include<fstream>
#include<vector>
#include<queue>
using namespace std;
fstream f1("dijkstra.in", ios::in);
fstream f2("dijkstra.out", ios::out);
int n, m, dist[50005], viz[50005];
vector<pair<int, int> > v[50005];
priority_queue < pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
int main(){

   int i, x, y, c, nod, cost;
   f1>>n>>m;
   for(i=1; i<=m; i++){
       f1>>x>>y>>c;
       v[x].push_back({y,c});
   }
   dist[1]=0;
   for(i=2; i<=n; i++) dist[i]=1e9+5;
   q.push({0,1});

   while(!q.empty()){
       nod=q.top().second;
       cost=q.top().first;
       viz[nod]=1;
       q.pop();

       if(dist[nod]==cost)
       for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
           if((!viz[(*it).first])&&(dist[(*it).first]> dist[nod]+(*it).second)){
               dist[(*it).first]= dist[nod]+(*it).second;
               q.push( {dist[(*it).first],  (*it).first});
       }

   }
   for(i=2; i<=n;i++)
       if(dist[i]< 1e9+5) f2<<dist[i]<< ' ';
       else f2<<0<<' ';
    return 0;
}