#include <bits/stdc++.h>

using namespace std;

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

const int INF = 2e9;

struct muchie
{
    int Y, cost;
}A;

int n, m, x, y, C;

int NOD;

vector <muchie> v[50001];
vector <int> dist(50001, INF);

void dijkstra (int nod)
{

    bitset <50001> viz;
    dist[nod] = 0;
    priority_queue< pair <int, int>, vector< pair <int, int> >, greater <pair <int , int> > > q;
    q.push(make_pair(nod, 0));
    while(!q.empty())
    {
        NOD = q.top().first;
        viz[NOD] = 1;
        q.pop();
        for (vector <muchie> :: iterator i=v[NOD].begin(); i!=v[NOD].end(); i++)
        {
            A = *i;
            if (dist[NOD] + A.cost < dist[A.Y])
            {
                dist[A.Y] = dist[NOD] + A.cost;
                if (viz[A.Y] == 0)
                {
                    q.push(make_pair(A.Y, dist[A.Y]));
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i=0; i<m; i++)
    {
        fin >> x >> A.Y >> A.cost;
        v[x].push_back(A);
    }
    dijkstra(1);
    for (int i=2; i<=n; i++)
        if (dist[i] == INF) fout << "0 ";
        else fout << dist[i] << " ";
    return 0;
}