#include<iostream>
#include<string>
#include<set>
#include<vector>
#include<algorithm>
#include<ctime>

using namespace std;

#define NM 50005
#define inf 2000000000
#define PB push_back
#define MKP make_pair

vector<pair<int,int> > G[NM];

set<pair<int,int> > H;
set<pair<int,int> >::iterator it; 

int COST[NM],N,M,S;

char isin[NM];

int main()
{
    int start=clock();
    
    int a,b,c;
    
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d %d",&N,&M);
    
    S=1;
    
    for(int i=1;i<=M;++i)
    {
        scanf("%d %d %d",&a,&b,&c);    
        G[a].PB(MKP(b,c));
    }
    
    for(int i=1;i<=N;++i)
       COST[i]=inf;
    
    COST[S]=0;
    
    for(int i=1;i<=N;++i)
    {
       H.insert(MKP(COST[i],i));
       isin[i]=1;
    }   
       
    while(!H.empty())
    {
       it=H.begin();
       
       int cost=it->first;
       int nod=it->second;
       
       H.erase(it);
       isin[nod]=0;
       
       for(int i=0;i<G[nod].size();++i)
       {
            int nnod=G[nod][i].first; 
            int ncost=G[nod][i].second;
            
            if(COST[nnod]>COST[nod]+ncost)
            {
                it=H.find(MKP(COST[nnod],nnod));
                H.erase(it);
                
                COST[nnod]=COST[nod]+ncost;
                H.insert(MKP(COST[nnod],nnod));                          
            }  
       }              
    }   
    
    for(int i=2;i<=N;++i)
       if(COST[i]==inf) printf("0 "); 
       else printf("%d ",COST[i]);
    
    int stop=clock();
    
    //printf("\n%lf",(double)(stop-start)/CLOCKS_PER_SEC);
    
    return 0;
}