#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

#define nmax 50001
#define inf 1 << 30
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int i,n,m,a,b,x;
int c[nmax];
vector < pair <int, int> > v[nmax];
set < pair <int, int> > S;

void dij(){
    S.insert(make_pair(0,1));
    
    for (i=2; i<=n; i++) c[i]=inf;
    
    while(!S.empty()){
        int nod=(*S.begin()).second;
        int MIN=(*S.begin()).first;
        
        S.erase(S.begin());
        
        for (i=0; i<v[nod].size(); i++){
            int vecin=v[nod][i].first;
            int cost=v[nod][i].second;
            
            if (c[vecin]>MIN+cost){
                c[vecin]=MIN+cost;
                S.insert(make_pair(c[vecin], vecin));
            }
        }
    }
    
    for (i=2; i<=n; i++)
        if (c[i]==inf) g << 0 << " ";
        else g << c[i] << " ";
    
}

int main(){
    
    f >> n >> m;
    
    for (i=1; i<=m; i++)
        f >> a >> b >> x,
        v[a].push_back(make_pair(b,x));
    
    dij();
    
    return 0;
}