#include <iostream>
#include <fstream>
#include <vector>
#define INF 1000000010
#define NMAX 50010

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

struct Pair
{
    int y, c;
};

vector< Pair > a[NMAX];
struct Nod
{
    int value, nod;
    Nod * s, * d;
} * dp;

int n, m, v[NMAX];

inline void SetMin(Nod * p)
{
    p->value = (p->s->value < p->d->value) ? p->s->value : p->d->value;
    p->nod = (p->s->value < p->d->value) ? p->s->nod : p->d->nod;
}

void InitializareArbore(int ls, int ld, Nod * d)
{
    if (ls == ld)
    {
        d->nod = ls;
        d->value = INF;
    }
    else
    {
        d->nod = ls;
        d->value = INF;
        int m = (ls + ld) / 2;
        Nod * q = new Nod;
        d->s = q;
        q = new Nod;
        d->d = q;

        InitializareArbore(ls, m, d->s);
        InitializareArbore(m + 1, ld, d->d);
    }
}

void Delete(int ls, int ld, int nod, Nod * d)
{
    if (ls == ld)
    {
        d->value = 2 * INF;
        return;
    }
    int m = (ls + ld) / 2;
    if (nod > m)
        Delete(m + 1, ld, nod, d->d);
    else
        Delete(ls, m, nod, d->s);

    SetMin(d);
}
void ModifyNod(int ls, int ld, int nod, int value, Nod * d)
{
    if (ls == ld)
    {
        if (d->value == 2 * INF)
            return;
        if (d->value < value)
            return;
        d->value = value;
        return;
    }
    int m = (ls + ld) / 2;
    if (nod > m)
        ModifyNod(m + 1, ld, nod, value, d->d);
    else
        ModifyNod(ls, m, nod, value, d->s);

    SetMin(d);
}

void Dijkstra(int nod)
{
    v[nod] = dp->value;
    Delete(1, n, nod, dp);
    for (unsigned i = 0; i < a[nod].size(); i++)
    {
        Pair p = a[nod][i];
        ModifyNod(1, n, p.y, v[nod] + p.c, dp);
    }

    nod = dp->nod;
    if (dp->value == INF || dp->value == 2 * INF)
        return;
    Dijkstra(nod);
}

int main()
{
    f >> n >> m;
    dp = new Nod;
    dp->nod = 1;
    dp->value = INF;
    dp->s = NULL;
    dp->d = NULL;
    InitializareArbore(1, n, dp);
    for (int c, x, y, i = 0; i < m; i++)
    {
        f >> x >> y >> c;
        Pair p;
        p.y = y;
        p.c = c;
        a[x].push_back(p);
    }
    ModifyNod(1, n, 1, 0, dp);
    Dijkstra(1);
    for (int i = 2; i <= n; i++)
        g << v[i] << ' ';
    return 0;
}