#include <cstdio>
#include <vector>

#define NMAX 50010
#define INF 10000

using namespace std;

FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");

//ifstream fin("dijkstra.in");
//ofstream fout("dijkstra.out");

void dijkstra(int x);

vector <int> M[NMAX*5], Cost[NMAX], tata, d;
vector <bool> viz;
int n, p, x, y, c, i, minu, poz, m;
bool okay;

int main()
{
    fscanf(fin, "%d%d", &n, &m);//fin >> n >> m;
    for(i = 0;  i <= n; ++i)
    {
        viz.push_back(false);
        tata.push_back(p);
        d.push_back(INF);
    }
    d[1] = 0;
    for(i = 1; i <= m; ++i)
    {
        fscanf(fin, "%d%d%d", &x, &y, &c);//fin >> x >> y >> c;
        M[x].push_back(y);
        //M[y].push_back(x);
        Cost[x].push_back(c);
        //Cost[y].push_back(c);
    }
    dijkstra(1);
    for(i = 2; i <= n; ++i)
    if(d[i] != INF)
        fprintf(fout, "%d ", d[i]);//fout << d[i] << ' ';
    else
        fprintf(fout, "0 ");//fout << "0 ";

    return 0;
}


void dijkstra(int x)
{
    int i;
    for(i = 0; i < M[x].size(); ++i)
    {
        d[M[x][i]] = Cost[x][i];
    }
    tata[x] = 0;
    viz[x] = true;
    okay = true;
    while(okay)
    {
        minu = INF;
        for(i = 1; i <= n; ++i)
            if(viz[i] == false && minu > d[i])
        {
            minu = d[i];
            poz = i;
        }
        if(minu != INF)
        {
            viz[poz] = true;
            for(i = 0 ; i < M[poz].size(); ++i)
                if(viz[M[poz][i]] == false && d[M[poz][i]] > d[poz]+Cost[poz][i])
            {
                d[M[poz][i]] = d[poz]+Cost[poz][i];
                tata[M[poz][i]] = poz;
            }
        }
        else
            okay = false;
    }

}