#include <cstdio>
#include <cstring>
#include <vector>

#define INF 2000000
#define MAXN 50001
using namespace std;

int d[MAXN],fol[MAXN],n,m,i,j,a,b,c;
vector< pair<int,int> > graf[MAXN];
pair<int,int> p;

void rezolva();

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d %d",&n,&m); 
            
    for (i=1;i<=m;i++) {
	    scanf("%d %d %d",&a,&p.first,&p.second); 
        graf[a].push_back(p);
    }     
    
    rezolva();
    
    for (i=2;i<=n;i++)
        if (d[i]!=INF)
           printf("%d ",d[i]);
        else
            printf("0 ");
    
    printf("\n");
    
    return 0;
}

void rezolva(){
     int min,nod;
     
     for(i=1;i<=n;i++)
         d[i] = INF;
         
     for(vector< pair<int,int> >::iterator it = graf[1].begin(); it!=graf[1].end() ; it++)
                 d[(*it).first] = (*it).second;
     
     d[1]=0;
     fol[1]=1;
     
     while(1) {
              
		   min=INF;
		   
           for ( i = 1 ; i <= n ; i++ )
		       if ( d[i]<min && !fol[i] ) {
                    min = d[i];
                    nod = i;
		       }
           
		   if (min == INF)
		      break;
		      
		   fol[nod]=1;
           for (vector< pair<int,int> >::iterator it = graf[nod].begin() ; it!= graf[nod].end() ; it++ ) 
                if (d[(*it).first] > d[nod] + (*it).second) 
	                d[(*it).first] = d[nod] + (*it).second;
     }
}