#include <cstdio>

#define sqrInf 999999999999999999LL

using namespace std;

FILE *f, *g;

typedef long long lint;

lint dp[50009];

lint n, m;

lint k;

lint lst[50009];

lint nod[250009];
lint urm[250009];

lint c[250009];

lint nods;

lint h[50009];
lint poz[50009];

inline lint mna(lint a, lint b)
{
    return (a < b ? a : b);
}

void add(lint a, lint b, lint cost)
{
    k ++;

    nod[k] = b;
    urm[k] = lst[a];

    c[k] = cost;

    lst[a] = k;
}

void swapp(lint &a, lint &b)
{
    lint aux = a;
    a = b;
    b = aux;
}

void schimba(lint a, lint b)
{
    swapp(h[a], h[b]);
    swapp(poz[h[a]], poz[h[b]]);
}

bool cmp(lint a, lint b)
{
    return dp[h[a]] < dp[h[b]];
}

void readFile()
{
    f = fopen("dijkstra.in", "r");

    fscanf(f, "%lld%lld", &n, &m);

    lint a, b, c;

    while(m --)
    {
        fscanf(f, "%lld%lld%lld", &a, &b, &c);

        add(a, b, c);
    }

    fclose(f);
}

void upHeap(lint poz)
{
    while(poz > 1)
    {
        if(cmp(poz, poz / 2) == 1)
            schimba(poz, poz / 2);

        else
            return;
    }
}

void downHeap(lint poz)
{
    while(poz * 2 <= nods)
    {
        lint fiu = poz;

        if(poz * 2 <= nods)
        {
            if(cmp(poz * 2, fiu) == 1)
                fiu = poz * 2;
        }

        if(poz * 2 + 1 <= nods)
        {
            if(cmp(poz * 2 + 1, fiu) == 1)
                fiu = poz * 2 + 1;
        }

        if(fiu == poz)
            return;

        schimba(poz, fiu);
        poz = fiu;
    }
}

void adh(lint i, lint nr)
{
    nods ++;

    h[nods] = i;

    poz[i] = nods;

    upHeap(nods);
}

void dilit(lint poz)
{
    schimba(poz, nods);

    nods --;

    downHeap(poz);
}

void dijkstra()
{
    lint i;
    lint mn;
    lint p;

    for(i = 2; i <= n; i ++)
    {
        mn = h[1];

        dilit(1);

        for(p = lst[mn]; p != 0; p = urm[p])
        {
            dp[nod[p]] = mna(dp[nod[p]], dp[mn] + c[p]);
        }
    }
}

void solve()
{
    lint i;
    for(i = 2; i <= n; i ++)
        dp[i] = sqrInf;

    lint p;
    for(p = lst[1]; p != 0; p = urm[p])
    {
        dp[nod[p]] = c[p];
    }

    for(p = 2; p <= n; p ++)
    {
        adh(p, dp[p]);
    }

    dijkstra();
}

void printFile()
{
    g = fopen("dijkstra.out", "w");

    lint i;
    for(i = 2; i <= n; i ++)
        fprintf(g, "%lld ", dp[i]);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}