#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf 66666666
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m, a, b, c, cost[50003];
struct comp {
    bool operator() (const int &X, const int &Y) {
        return (cost[X] > cost[Y]);
    }
};
priority_queue<int, vector<int>,comp> q;
vector< pair<int, int> > lv[50003];
vector< pair<int, int> >::iterator it;
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; ++i){
        f>>a>>b>>c;
        lv[a].push_back(make_pair(b, c));
    }
    for(int i=1; i<=n; ++i) cost[i]=inf;
    cost[1]=0;
    q.push(1);
    while(q.size()){
        int x=q.top();
        q.pop();
        for(it=lv[x].begin(); it!=lv[x].end(); ++it)
            if(cost[(*it).first]>cost[x]+(*it).second)
               cost[(*it).first]=cost[x]+(*it).second, q.push((*it).first);
    }
    for(int i=2; i<=n; ++i)
        if(cost[i]!=inf) g<<cost[i]<<' ';
        else g<<0<<' ';
    return 0;
}