#include <fstream>
#include <iostream>
#include <vector>
#include <string.h>
#define INF (1<<25)
using namespace std;
struct muchie{
    int d,c;
};
int N,M,cost[500100]; vector<muchie> graf[50100]; bool viz[50100];
void calc_cost(){
    int i,j,k,MIN,nod;
    for (i=1; i<=N; i++){
        MIN=INF;
        for (j=1; j<=N; j++)
            if (!viz[j] && cost[j]<MIN) { MIN=cost[j]; nod=j; }
        viz[nod]=1;
        for (k=0; k<graf[nod].size(); k++)
            if (cost[nod]+graf[nod][k].c<cost[graf[nod][k].d]) cost[graf[nod][k].d]=cost[nod]+graf[nod][k].c;
    }
}
int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in >> N >> M;
    int i,x; muchie aux;
    for (i=0; i<M; i++){
        in >> x >> aux.d >> aux.c;
        graf[x].push_back(aux);
    }
    memset(viz,0,sizeof(viz));
    for (i=1; i<=N; i++) cost[i]=INF;

    cost[1]=0;
    calc_cost();
    for (i=2; i<=N; i++)
        if (cost[i]==INF) out << 0 << " ";
        else out << cost[i] << " ";
    return 0;
}