#include <fstream>
#include <vector>
#define INF 999999999

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct muchie
{
    int x, c;
};

struct drum
{
    int c, nr;
};

void push(drum d);
void update(int poz, int c);
drum popMin();

int n, m, nH, poz[50005], sol[50005];
vector<muchie> L[50005];
drum H[50005];

int main()
{
    int i, x, y, c;
    muchie aux;
    drum auxx;

    fin >> n >> m;
    for (i=1;i<=m;i++)
    {
        fin >> x >> aux.x >> aux.c;
        L[x].push_back(aux);
    }
    for (i=0;i<L[1].size();i++)
    {
        auxx.c = L[1][i].c;
        auxx.nr = L[1][i].x;
        push(auxx);
    }
    for (i=2;i<=n;i++)
        if (!poz[i])
        {
            auxx.c = INF;
            auxx.nr = i;
            push(auxx);
        }
    while (nH)
    {
        auxx = popMin();
        sol[auxx.nr] = auxx.c;
        for (i=0;i<L[auxx.nr].size();i++)
        {
            y = L[auxx.nr][i].x;
            c = L[auxx.nr][i].c;
            if (H[poz[y]].c > auxx.c + c)
                update(poz[y],auxx.c+c);
        }
    }
    for (i=2;i<=n;i++)
        fout << sol[i] << ' ';
    fout << '\n';
    return 0;
}

void push(drum d)
{
    int fiu, tata;

    fiu = ++nH;
    tata = fiu/2;
    while (d.c < H[tata].c && tata)
    {
        poz[H[tata].nr] = fiu;
        H[fiu] = H[tata];
        fiu = tata;
        tata = fiu/2;
    }
    H[fiu] = d;
    poz[d.nr] = fiu;
}

void update(int pozz, int c)
{
    int fiu, tata;
    drum aux;

    aux = H[pozz];
    aux.c = c;
    fiu = pozz;
    tata = fiu/2;
    while (aux.c < H[tata].c && tata)
    {
        poz[H[tata].nr] = fiu;
        H[fiu] = H[tata];
        fiu = tata;
        tata = fiu/2;
    }
    H[fiu] = aux;
    poz[aux.nr] = fiu;
}

drum popMin()
{
    int fiu, tata;
    drum rez = H[1], aux;

    H[1] = H[nH--];
    aux = H[1];
    tata = 1;
    while (1)
    {
        fiu = 2*tata;
        if (fiu > nH)
            break;
        if (H[fiu].c > H[fiu+1].c && fiu<n)
            fiu++;
        if (aux.c < H[fiu].c)
            break;
        H[tata] = H[fiu];
        poz[H[tata].nr] = tata;
        tata = fiu;
    }
    H[tata] = aux;
    poz[aux.nr] = tata;
    return rez;
}