#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()(const int &x, const int &y){
      return d[x]>d[y];
  }

};

priority_queue <int, vector<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(1);
 while(!heap.empty()){
    int    nod=heap.top();
     heap.pop();
     if(viz[nod]==1)
        continue;
     viz[nod]=1;
   for(i=0;i<G[nod].size();i++){
       int nod_act=G[nod][i].first;
       int cost= G[nod][i].second;
       if(viz[nod_act]==0&&d[nod_act]>d[nod]+cost){
           d[nod_act]=d[nod]+cost;
           heap.push(nod_act);
       }


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

    return 0;
}