#include <fstream>
#include<vector>
#include<queue>
#define inf 2000000000
using namespace std;
vector< pair <int,int> >G[50002] ;
int n,m,i,x,y, d[50002];
bool viz[50002];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct compare {
  bool operator()(pair<int, int> &x, pair<int, int> &y){
      return x.second>y.second;
  }

};

priority_queue <pair<int, int>, vector<pair <int,int> >, compare> heap;

int main()
{
    int c;
f>>n>>m;
for(i=1;i<=m;i++)
{
    f>>x>>y>>c;
    G[x].push_back(make_pair(y,c));

}
d[1]=0;
for(i=2;i<=n;i++)
   d[i]=inf;
 heap.push(make_pair(1,0));
 while(!heap.empty()){
    pair<int,int>   nod=heap.top();
     heap.pop();
     if(viz[nod.first]==1)
        continue;
     viz[nod.first]=1;
   for(i=0;i<G[nod.first].size();i++){
       int nod_act=G[nod.first][i].first;
       int cost= G[nod.first][i].second;
       if(viz[nod_act]==0&&d[nod_act]>nod.second+cost){
           d[nod_act]=nod.second+cost;
           heap.push(make_pair(nod_act, d[nod_act]));
       }


   }
 }
 for(i=2;i<=n;i++)
    if(d[i]==inf)
       g<<0<<" ";
       else
        g<<d[i]<<" ";

    return 0;
}