#include <iostream>
#include<fstream>
#include<vector>
#define inf 2000000

using namespace std;

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

int n, m, dist[50000];

struct muchie
{
    int nod1;
    int nod2;
    int cost;
};

muchie v[50000];

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].nod1 >> v[i].nod2 >> v[i].cost;
        if(v[i].nod1 == 1) dist[v[i].nod2] = v[i].cost;
    }
    for(int i = 1; i <= n; i++)
        if(dist[i]==0)
            dist[i] = inf;
}

void dijkstra()
{
    bool ok = true;
    while(ok == true)
    {
        ok = false;
        for(int i = 1; i <= m; i++)
        {
            if(dist[v[i].nod1] + v[i].cost < dist[v[i].nod2])
            {
                dist[v[i].nod2] = dist[v[i].nod1] + v[i].cost ;
                ok = true;
            }
        }
    }
}

int main()
{
    citire();
    dijkstra();
    for(int i = 2; i <= n; i++)
        fout << dist[i] << " ";
    return 0;
}