#include <cstdio>
#include <vector>

using namespace std;

long n, m, i, j, heap[100100] ,poz[50100], cs[50100], nod, fiu, a, b, cc, inf, l, k;

vector <int> v[50100];
vector <int> c[50100];


inline void swap(int i, int j){
    int aux;
    aux=heap[i];
    heap[i]=heap[j];
    heap[j]=aux;    
}

void heap_down(int x){
    
    int p=x;    
    
    while (2*p<=k)
        if ((cs[heap[2*p]]<cs[heap[p]])||(cs[heap[2*p+1]]<cs[heap[p]]))
            
            if (cs[heap[2*p]]<cs[heap[2*p+1]]){
                
                swap(p,2*p);
                
                poz[heap[p]]=p;
                poz[heap[2*p]]=2*p;    
                
                p=2*p;
            }    
            else {
                
                swap(p,2*p+1);
                
                poz[heap[p]]=p;
                poz[heap[2*p+1]]=2*p+1;
                
                p=2*p+1;
                
            }
        else
            break;
    
}

void heap_up(int x){
    
    int p=x;
    
    while (p>1)
        if (cs[heap[p]]<cs[heap[p/2]]){
            
            swap(p,p/2);
            
            poz[heap[p]]=p;
            poz[heap[p/2]]=p/2;
            
            p/=2;    
        }    
        else
            break;
}



int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    
    l=n;
    
    for (i=1;i<=m;i++){
        scanf("%d%d%d", &a, &b, &cc);
        v[a].push_back(b);
        c[a].push_back(cc); 
        
    }
        
    inf=1000000000;
    
    heap[1]=1;
    poz[1]=1;
    
    for (i=1;i<=l;i++){
        cs[i]=inf;
        heap[i]=i;
        poz[i]=i;
    }
        
    cs[0]=inf;    
    
    cs[1]=0;    
        
    k=l;
    
    while (k>0){
        
        nod=heap[1];
        
        for (i=0;i<v[nod].size();i++){
            
            fiu=v[nod][i];
            
            if (cs[nod]+c[nod][i]<cs[fiu]){
                
                cs[fiu]=cs[nod]+c[nod][i];
                
                heap_up(poz[fiu]);                    
            }
        }
        
        swap(1, k);
        heap[k]=0;
        k--;
        
        heap_down(1);
        
    }        
       
    for (i=2; i<=n; i++)
        if (cs[i]==inf)
            printf("0 ");
        else
            printf("%d ",cs[i]);
        
    return 0;
}