# include <bits/stdc++.h>
# define INF 999999999
# define NR 100005
# define mp make_pair
# define f first
# define s second
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <pair <int, int> > v[NR], HEAP;
int n,m,x,y,cost;
int drum[NR];
bool cmp (pair <int, int> x, pair <int, int> y) {
    return (x.f > y.f);
}
void baga (int cost, int x) {
    HEAP.push_back(mp(cost, x));
    push_heap(HEAP.begin(), HEAP.end(), cmp);
}
void scoate () {
    pop_heap(HEAP.begin(), HEAP.end(), cmp);
    HEAP.pop_back();
}
void dijkstra() {
    while (HEAP.size()) {
        int X=HEAP[0].f;
        int cact=HEAP[0].s;

        scoate();

        if (cact != drum[X]) continue;

        for (auto &x: v[X]) {
            if (cact + x.s < drum[x.f]) {
                drum[x.f]=cact + x.s;

                baga(x.f, drum[x.f]);
            }
        }
    }
}
int main ()
{
    f>>n>>m;
    for (int i=1; i<=m; ++i) {
        f>>x>>y>>cost;

        v[x].push_back(mp(y, cost));
    }

    for (int i=2; i<=n; ++i) {
        drum[i]=INF;
    }

    baga (1, 0);
    dijkstra ();

    for (int i=2; i<=n; ++i) {
        if (drum[i]==INF) g<<"0 ";
                     else g<<drum[i]<<" ";
    }
    g<<"\n";

    return 0;
}