#include <bits/stdc++.h>
#define NMAX 50005

using namespace std;

FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");

struct infoNod{
    int value;
    unsigned short int index;
    friend bool operator >(infoNod a, infoNod b);
};
bool operator >(infoNod a, infoNod b){
    return a.value > b.value;
}
priority_queue<infoNod, vector<infoNod>, greater<infoNod> > heapOfNodes;
void dijkstra(int);

int n, m, i, x, y, weigthEdge, costMinim[NMAX];
bool uz[NMAX];
vector<int> vecini[NMAX], cost[NMAX];

int main(){
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; ++i){
        fscanf(fin, "%d%d%d", &x, &y, &weigthEdge);
        vecini[x].push_back(y);
        cost[x].push_back(weigthEdge);
        }
    for(i=2; i<=n; ++i)
        costMinim[i] = 1e9;
    dijkstra(1);
    for(i=2; i<=n; ++i){
        if(costMinim[i] == 1e9)
            costMinim[i] = 0;
        fprintf(fout, "%d ", costMinim[i]);
        }
    fprintf(fout, "\n");
    return 0;
}

void dijkstra(int k){
    int i;
    infoNod urm;
    if(uz[k] == 0){
        uz[k] = 1;
        for(i=0; i<vecini[k].size(); ++i){
            if(uz[vecini[k][i]] == 0){
                if(costMinim[k] + cost[k][i] < costMinim[vecini[k][i]]){
                    costMinim[vecini[k][i]] = costMinim[k] + cost[k][i];
                    urm.index = vecini[k][i];
                    urm.value = costMinim[vecini[k][i]];
                    heapOfNodes.push(urm);
                    }
                }
            }
        }
    if(heapOfNodes.empty()) return;
    urm = heapOfNodes.top();
    heapOfNodes.pop();
    dijkstra(urm.index);
}