/// Problema "Dijkstra" - InfoArena
#include <cstdio>
#include <algorithm>
#include <vector>

#define in "dijkstra.in"
#define out "dijkstra.out"
#define NMAX (50000 + 7)
#define pb push_back
#define inf (1000000000 + 7)

using namespace std;
int N, M, H[NMAX], loc[NMAX], len, Rloc[NMAX], aux, sol[NMAX];
struct muchie
{
    int vecin;
    int lungime;
} tmp;
vector <muchie> adj[NMAX];

int upheap(int key)
{
    while(key > 1)
    {
        if(H[key] < H[(key>>1)])
        {
            swap(H[key], H[(key>>1)]);
            loc[Rloc[key]] = (key>>1);
            loc[Rloc[(key>>1)]] = key;
            swap(Rloc[key], Rloc[(key>>1)]);
            key = (key>>1);
        }
        else break;
    }
    return key;
}
inline void downheap(int key)
{
    while(((key<<1)|1) <= len)
    {
        if(H[key] < min(H[(key<<1)], H[((key<<1)|1)])) break;
        if(H[(key<<1)] < H[((key<<1)|1)])
        {
            swap(H[key], H[(key<<1)]);
            loc[Rloc[key]] = (key<<1);
            loc[Rloc[(key<<1)]] = key;
            swap(Rloc[key], Rloc[(key<<1)]);
            key = (key<<1);
            continue;
        }
        swap(H[key], H[((key<<1)|1)]);
        loc[Rloc[key]] = ((key<<1)|1);
        loc[Rloc[((key<<1)|1)]] = key;
        swap(Rloc[key], Rloc[((key<<1)|1)]);
        key = ((key<<1)|1);
    }
    if((key<<1) == len)
    {
        swap(H[key], H[(key<<1)]);
        loc[Rloc[key]] = (key<<1);
        loc[Rloc[(key<<1)]] = key;
        swap(Rloc[key], Rloc[(key<<1)]);
        key = (key<<1);
    }
}
inline void insert(int key, int value)
{
    ++len;
    H[len] = value;
    loc[key] = len;
    Rloc[len] = key;
    upheap(len);
}
inline void elimin(int key)
{
    swap(H[key], H[len]);
    loc[Rloc[key]] = len;
    loc[Rloc[len]] = key;
    swap(Rloc[key], Rloc[len]);
    loc[Rloc[len]] = 0;
    --len;
    key = upheap(key);
    downheap(key);
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d", &N, &M);
    for(; M; --M)
    {
        scanf("%d %d %d", &aux, &tmp.vecin, &tmp.lungime);
        adj[aux].pb(tmp);
    }
    insert(1, 0);
    for(int i = 2; i<= N; ++i) insert(i, inf);
    while(len)
    {
        int p = Rloc[1];
        sol[p] = H[1];
        elimin(1);
        int sze = adj[p].size();
        for(int i = 0; i< sze; ++i)
        {
            if(H[loc[adj[p][i].vecin]] <= sol[p] + adj[p][i].lungime) continue;
            elimin(loc[adj[p][i].vecin]);
            insert(adj[p][i].vecin, sol[p] + adj[p][i].lungime);
        }
    }
    for(int i = 2; i<= N; ++i) printf("%d ", sol[i]);
    printf("\n");
    return 0;
}