#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;

struct ce{
       int n,d;
       };

void du(int k);
void de(int k);
vector<int> p(1);
vector<ce> h;

main(){
       int n,m,a,b,di;
       const int inf=1<<30;
       ifstream cinr ("dijkstra.in");
       ofstream cour ("dijkstra.out");
       cinr >> n;
       cinr >> m;
       vector< vector<int> > g(n+1);
       int d[n+1];
       for(int i=1; i<=m; i++){
               cinr >> a;
               cinr >> b;
               cinr >> di;
               g[a].push_back(b);
               g[a].push_back(di);
               }
       ce c;
       c.n=0; c.d=-1;
       h.push_back(c);
       for(int i=1; i<=n; i++){
               d[i]=inf;
               c.d=inf;
               c.n=i;
               p.push_back(i);
               h.push_back(c);
               }
       d[1]=0;
       h[1].d=0;
       int y;
       //for(int i=1; i<h.size(); i++){cout << h[i].d << " " << h[i].n << " " << p[i] << "\n";}
       //cin.ignore(2);
       while(h.size()>1){
                         y=h[1].n;
                         p[h[h.size()-1].n]=1;
                         h[1]=h[h.size()-1];
                         h.pop_back();
                         de(1);
                         for(int i=0; i<g[y].size(); i+=2){
                                 if(d[g[y][i]]>d[y]+g[y][i+1]){
                                                                  d[g[y][i]]=d[y]+g[y][i+1];
                                                                  h[p[g[y][i]]].d=d[y]+g[y][i+1];
                                                                  du(p[g[y][i]]);
                                                                  }
                                 }
                         }
       //for(int i=1; i<h.size(); i++){cout << h[i].d << " " << h[i].n << " " << p[i] << "\n";}
       for(int i=2; i<=n; i++){ 
               if(d[i]>=inf){ cour << "0 "; }
               else         { cour << d[i] << " "; }
               }
       //cin.ignore(1);
       cinr.close();
       cour.close();
       }

void du(int k){
     ce c;
     int i=k,y,u;
     while(h[i/2].d>h[i].d){
                            y=i/2;
                            u=p[h[i].n];
                            p[h[i].n]=p[h[y].n];
                            p[h[y].n]=u;
                            c=h[i];
                            h[i]=h[y];
                            h[y]=c; 
                            i=y;
                            }
     }

void de(int k){
     ce c;
     int i=k,y,u; 
     while(2*i+1<h.size()){
                           y=2*i;
                           if(h[y].d>h[y+1].d) y++;
                           if(h[i].d>h[y].d){
                                         u=p[h[i].n];
                                         p[h[i].n]=p[h[y].n];
                                         p[h[y].n]=u;
                                         c=h[i];
                                         h[i]=h[y];
                                         h[y]=c;                                         
                                         }
                           else          { return; }
                           i=y;
                           }
     y=2*i;
     if(y<h.size()){
                    if(h[i].d>h[y].d){
                                  u=p[h[i].n];
                                  p[h[i].n]=p[h[y].n];
                                  p[h[y].n]=u;
                                  c=h[i];
                                  h[i]=h[y];
                                  h[y]=c;                                         
                                  }  
                    }
     
     }