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

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

int n,m,i,dis[nmax];
vector < pair <int, int> > vec[nmax];
set < pair <int, int> > S;

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

int main(){
    in >> n >> m;
    int a,b,c;
    for (i=1; i<=n; i++)
        in >> a >> b >> c,
        vec[a].push_back(make_pair(b, c));
    dijkstra();
    return 0;
}