#include <iostream>
#include<fstream>
using namespace std;

#define nmax 10000
#define INF 9999999

ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
int src, dest, val, n, m, minn, crt;
int cost [nmax][nmax], viz[nmax], parent[nmax], dist[nmax];
void citire()
{

    fin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        fin >> src >> dest >> val;
        cost[src][dest]=val;
    }

}

void Dijkstra(int src)
{
    for(int i = 1 ; i <= n ; ++i)
    {
        dist[i] = INF;
        parent[i] = 0;
        viz[i] = 0;
    }
    dist[src] = 0;
    for (int i = 1; i <= n - 1; ++i)
    {
        minn = INF;
        crt = -1;
        for(int j = 1; j <= n; ++j)
        {
            if(!viz[j] && dist[j] < minn)
            {
                minn=dist[j];
                crt=j;
            }
        }
        if(crt == -1)
            break;

        viz[crt]=1;
        for(int j = 1; j <= n; ++j)
        {
            if(cost[crt][j] == 0) continue;

            dist[j] = dist[j] < dist[crt] + cost[crt][j] ? dist[j] : dist[crt] + cost[crt][j];
        }

    }
}
void afis()
{
    for(int i = 1; i < n; ++i)
    {
        if (dist[i+1] == INF)
            fout << 0 << " ";
        else
            fout << dist[i+1] << " ";
    }
}
int main()
{
    citire();
    Dijkstra(1);
    afis();
    return 0;
}