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

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

int n, m, x, y, c, vis[nmax], pasi[nmax];

typedef struct poz{
    int nod, cost;
}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>>c;
        adj[x].push_back({y , c});
    }
    
    
    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 vecin : adj[nod]){
            if(vis[vecin.nod] == 0 && cost + vecin.cost < pasi[vecin.nod]){
                
                pasi[vecin.nod] = cost + vecin.cost;
                pq.push({vecin.nod , pasi[vecin.nod]});
                
            }
        }
        
        
    }
    
    for(int i=2;i<=n;i++){
        if(pasi != INF){
            fout<<pasi[i]<<" ";
        }else{
            fout<<0<<" ";
        }
    }
    
    
    
}