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

fin = fopen("dijkstra.in", "r");
fout = fopen("dijkstra.out", "w");
fscanf(fin,"%d%d", &nrvertex, &m);
for(i=1;i<=m;i++){
    fscanf(fin,"%d%d%d", &x, &y, &w);
    nodes[x].push_back(y);
    weights[x].push_back(w);
    nodes[y].push_back(x);
    weights[y].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++)
fprintf(fout,"%d ", cost[i]);


fclose(fin);
fclose(fout);

    return 0;
}