#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#define N 50005
#define INF (1<<30)
using namespace std;
ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,L[N],x,y,c,i,vecinu,vama,io;
vector < pair<int,int> > v[N];
struct comp{
bool operator()(int x,int y)
{
    return L[x]>L[y];
}};
priority_queue <int,vector<int>,comp> kyu;
bool aici_boss[N];
int main()
{
    in>>n>>m;
    for(i=1;i<=n;i++){
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    for(i=1;i<=n;i++) L[i] = INF;
    L[1] = 0; kyu.push(1); aici_boss[1] = 1;
    while(!kyu.empty()){
        io = kyu.top();
        kyu.pop();
        aici_boss[io] = 0;
        for(size_t j=0;j<v[io].size();++j){
            vecinu = v[io][j].first;
            vama = v[io][j].second;
            if(L[io] + vama< L[vecinu]){
                L[vecinu] = L[io] + vama;
                if(!aici_boss[vecinu])
                kyu.push(vecinu),aici_boss[vecinu] = 1;
            }
        }
    }
    for(i=2;i<=n;i++) if(L[i]!=INF)out<<L[i]<<" "; else out<<"0 ";
    return 0;
}