#include <fstream>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
struct nod { int y, c;
             nod* urm; } *v[50001];
int n, m, i, j, k,d[50001],f[50001];
const int inf = 1000000000;
void AdNod(int i, int j, int k)
{
    nod* q;
    q = new nod;
    q->y = j;
    q->c = k;
    q->urm = v[i];
    v[i] = q;
}
void Dijkstra(int p)
{
    nod* q;
    int mi,i,j;
    q = v[p];
    d[0] = inf;
    d[p] = 0;
    f[p] = 1;
    while (q != NULL)
    {
        d[q->y] = q->c;
        q = q->urm;
    }
    for (i = 1; i < n; i++)
    {
        mi = 0;
        for (j = 1; j <= n; j++)
            if (f[j] == 0 && d[j] < d[mi])
                mi = j;
        if (mi > 0)
        {
            f[mi] = 1;
            q = v[mi];
            while (q != NULL)
            {
                if (d[q->y] > d[mi] + q->c)
                    d[q->y] = d[mi] + q->c;
                q = q->urm;
            }
        }
    }
}
int main()
{
    fi >> n >> m;
    for (i = 1; i <= n; i++)
    {
        v[i] = NULL;
        d[i] = inf;
    }
    while (fi >> i >> j >> k)
        AdNod(i, j, k);
    Dijkstra(1);
    for (i = 2; i <= n; i++)
    {
        if (d[i] == inf)
            fo << 0 << " ";
        else fo << d[i] << " ";
    }
    return 0;
}