#include <fstream>
#include <set>
#include <vector>
#include <cstring>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int nmax = 50005, INF = 0x3f3f3f3f;

vector<pair<int, int> >G[nmax];

int d[nmax];

int main(){
int n,m;

f>>n>>m;

for(int i=1;i<=m;++i){
    int from, to,cost;
    f>>from>>to>>cost;
    G[from].push_back(make_pair(to,cost));
}

memset(d, INF, sizeof d);

d[1] = 0;

set<pair<int, int> >h;

h.insert(make_pair(0,1));

while(!h.empty()){
    int node = h.begin()->second;
    h.erase(h.begin());
    for(vector<pair<int, int> >::iterator it = G[node].begin(); it != G[node].end(); ++it){
        int to = it->first;
        int cost = it->second;
        if(d[to] > d[node] + cost){
            if(d[to] != INF)
                h.erase(h.find(make_pair(d[to],to)));

            d[to] = d[node] + cost;
            h.insert(make_pair(d[to],to));
        }
    }
}

for(int i = 2; i <= n; ++i)
    d[i] != INF ? g<<d[i]<<" " : g<<0<<" ";

    g<<'\n';

return 0;
}