#include <bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int const NMAX = 5e4 +100;

struct edge{
    int n, c;
};

struct drum{
    int n, c;
};

class cmp{
    public:
        bool operator() (drum a, drum b){
            return a.c>b.c;
        }
};

vector<edge> graf[NMAX];
priority_queue< drum, vector<drum>, cmp> heap;
int viz[NMAX];

void dijkstra(int n){
    for (auto x: graf[n])
        heap.push({x.n, x.c});
    while (!heap.empty()){
        drum d=heap.top();
        if (viz[d.n] < d.c && viz[d.n]) goto sf;
        viz[d.n]=d.c;
        for (auto x: graf[d.n])
            if (!viz[x.n]) heap.push({x.n, d.c+x.c});
        sf: heap.pop();
    }
}

int main(){
    int i, n, m, n1, n2, c;
    in >> n >> m;
    for (i=1; i<=m; i++){
        in >> n1 >> n2 >> c;
        graf[n1].push_back({n2, c});
    }
    dijkstra(1);
    for (i = 2; i<=n; i++)
        out << viz[i] << ' ';
}