#include <fstream>
#define inf 100000000

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

int a[1500][1500], sel[1500], d[1500], i, m, n, j, c, cost, s, x,y;

void Dijkstra(int s)
{
    int mini, dn, jmin, j;
    for (i=1; i<=n; i++)
        d[i]=a[s][i];
    sel[s]=1;
    d[s] = 0;
    for (i=1; i<=n-2; i++)
    {
        mini = inf;
        for (j=1; j<=n; j++)
            if (sel[j] == 0)
                if (d[j]< mini)
                {
                    mini = d[j];
                    jmin = j;
                }
        sel[jmin]=1;
        for (j=1; j<=n; j++)
            if (sel[j]==0)
            {
                dn=d[jmin]+a[jmin][j];
                if (dn < d[j])
                    d[j]=dn;
            }
    }
}
int main ()
{
    f >> n >> m;
    for (i=1; i<=n; i++)
        for (j = 1; j <= n; j++)
            a[i][j] = inf;
    for (i=1; i<=m; i++)
    {
        f >> x >> y;
        f >> a[x][y];
    }
    Dijkstra(1);
    for (i = 2; i <= n; i++)
        if(d[i] == inf) g << "0 "<<' ';
        else  g << d[i] << ' ';
    g<<endl;
    return 0;
}