//Dijkstra (ai grija la variabilele din for 'i' pt functiile int)-> corect
#include <bits/stdc++.h>
using namespace std;
const int nmax = 50001;
const int mmax = 250001;
const int val_max = 99999;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N, M, i, j, a, b, c, dist[nmax], vis[nmax];

typedef struct poz{
    int nod, cost;
}student1;

vector<student1>v[nmax];


int minDist(int dist[], int vis[]){
    int minn=999999 , nod=0;
    
    for(int l=1;l<=N;l++){
        if(vis[l]==0 && dist[l]<=minn){ 
            nod = l;
            minn = dist[l];
        }
    }
    
    return nod;
}


int main()
{
   
    fin>>N>>M;
    for(i=1;i<=M;i++){
        fin>>a>>b>>c;
        v[a].push_back({b,c});
       // v[b].push_back({a,c});
    }
    
    for(i=1;i<=N;i++){
        dist[i] = val_max;
        vis[i] = 0;
    }
    
    //Dijkstra 
    dist[1] = 0;
    
    for(i=1;i<=N;i++){
        int u = minDist (dist, vis);
        
        vis[u] = 1;
        
        for(auto j : v[u]){
            
            if(vis[j.nod]==0 && dist[u]!=val_max && dist[u]+j.cost<dist[j.nod]){
                dist[j.nod] = dist[u] + j.cost;
            }
        }
        
        
    }
   
    for(i=2;i<=N;i++){
        if(dist[i]==val_max){
            cout<<0<<" ";
        }else{
            cout<<dist[i]<<" ";
        }
    }
   
    
}