#include <bits/stdc++.h>
using namespace std;
const int nmax = 50005, INF = 20000*50000;

int N, M, vis[nmax], pasi[nmax], x, y, z;

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

typedef struct poz{
    int nod, c;
}student;
vector < student > adj[nmax];


struct coord
{
    int nod, cost;
    
    const bool operator <(const coord &other)const{
        return cost > other.cost;
    }
};
priority_queue < coord > pq;



int main()
{
    fin>>N>>M;
    
    for(int i=1;i<=M;i++){
        fin>>x>>y>>z;
        adj[x].push_back({y , z});
    }
    
    for(int i=1;i<=N;i++){
        pasi[i] = INF;
    }
    
    pq.push({1 , 0});
    pasi[1] = 0;
    
    
    
    while(!pq.empty()){
        
        int nod = pq.top().nod, cost = pq.top().cost;
        pq.pop();
        
        if(vis[nod] == 1) continue;
        
        vis[nod] = 1;
        
        for(auto elem : adj[nod]){
            
            if(vis[elem.nod] == 0 && pasi[elem.nod] > cost + elem.c){
                pasi[elem.nod] = cost + elem.c;
                pq.push({elem.nod , pasi[elem.nod]});
            }
            
        }
        
    }
    
    
    for(int i=2;i<=N;i++){
        if(pasi[i]!=INF){
            fout<<pasi[i]<<" ";
        }else{
            fout<<0<<" ";
        }
    }
    
}