#include <fstream>
#define NMAX 2000000000
using namespace std;
long long a[5005][5005], d[5005], n, m, k, i, minn, x, y, c, j;
bool viz[5005], ok;
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            a[i][j] = NMAX;
    while(f >> x >> y >> c)
        a[x][y] = c;
    for(i = 2; i <= n; ++ i)
        d[i] = a[1][i];
    viz[1] = 1;
    d[1] = 0;
    ok = 1;
    while(ok != 0)
    {
        minn = NMAX;
        for(i = 2; i <= n; ++ i)
            if(viz[i] == 0 && d[i] < minn)
            {
                minn = d[i];
                k = i;
            }
        if(minn != NMAX)
        {
            viz[k] = 1;
            for(i = 2; i <= n; ++ i)
                if(viz[i] == 0 && d[i] > d[k] + a[k][i])
                    d[i] = d[k] + a[k][i];
        }
        else
            ok = 0;
    }
    for(i = 2; i <= n; ++ i)
        if(d[i] == NMAX)
            g << "0" << " ";
        else
            g << d[i] << " ";
    return 0;
}