#include <cstdio>

#define sqrInf 999999999999999999LL

using namespace std;

FILE *f, *g;

typedef long long lint;

lint dp[50009];

int n, m;

int k;

int lst[50009];

int nod[250009];
int urm[250009];

int c[250009];

int nods;

int h[50009];
int poz[50009];

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

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

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

    c[k] = cost;

    lst[a] = k;
}

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

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

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

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

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

    int a, b, c;

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

        add(a, b, c);
    }

    fclose(f);
}

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

        else
            return;
    }
}

void downHeap(int poz)
{
    while(poz * 2 <= nods)
    {
        int 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(int i, int nr)
{
    nods ++;

    h[nods] = i;

    poz[i] = nods;

    upHeap(nods);
}

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

    nods --;

    downHeap(poz);
}

void dijkstra()
{
    int i;
    int mn;
    int 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()
{
    int i;
    for(i = 2; i <= n; i ++)
        dp[i] = sqrInf;

    int 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");

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

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}