#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int cost[50001];
int queue[50001];
vector <short> nodes[250001];
vector <short> weights[250001];
int main() {
    FILE *fin, *fout;
    int m, i, j, nrvertex, back, front, node;
    short x, y, w;

fin = fopen("dijkstra.in", "r");
fout = fopen("dijkstra.out", "w");
fscanf(fin,"%d%d", &nrvertex, &m);
for(i=1;i<=m;i++){
    fscanf(fin,"%hd%hd%hd", &x, &y, &w);
    nodes[x].push_back(y);
    weights[x].push_back(w);

}


cost[1]=0;

for(i=2;i<=nrvertex;i++)
cost[i]=1000000000;

queue[1]=1;
back=1;
front=1;


while(back<=front){
node=queue[back];
for(j=0;j<nodes[node].size();j++){


queue[++front]=nodes[node][j];
if(cost[node] + weights[node][j] < cost[nodes[node][j]]){
queue[front]=nodes[node][j];
cost[nodes[node][j]] = cost[node] + weights[node][j];

}
else
queue[front--]=0;


}
back++;
}
for(i=2;i<=nrvertex;i++){
if(cost[i]!=1000000000)
fprintf(fout,"%d ", cost[i]);
else
fprintf(fout,"0 ");
}

fclose(fin);
fclose(fout);

    return 0;
}