#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define O 50010
#define oo 2147483627
using namespace std;

vector <pair <int, int> > G[O];
priority_queue <pair <int, int> > pq;
int dist[O];
int N, M, k;

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

void citire()
{
    in >> N >> M;
    int x, y, c;
    for(int i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        G[x].emplace_back(y, c);
//        G[y].emplace_back(x, c);
    }
}

void dijkstra(int z)
{
    int cost, nod;
    for(int i = 1; i <= N; i++)
        dist[i] = oo;
    dist[z] = 0;

    pq.push(make_pair(0, z));
    while(!pq.empty())
    {
        nod = pq.top().second;
        cost = -pq.top().first;
        pq.pop();
//        cout << nod << ' ' << cost << endl;

        if(dist[nod] != oo && nod != z)
            continue;

        dist[nod] = cost;
        for(int i = 0; i < G[nod].size(); i++)
            if(dist[G[nod][i].first] > cost + G[nod][i].second)
                pq.push(make_pair(-(cost + G[nod][i].second), G[nod][i].first));

    }
}

int main()
{
    citire();
//    for(int i = 1; i <= N; i++)
//    {
//        for(int j = 0; j < G[i].size(); j++)
//            out << G[i][j].first << G[i][j].second << ' ';
//        out << endl;
//    }

    dijkstra(1);

    for(int i = 2; i <= N; i++)
        if(dist[i] == oo)
            out << '0' << ' ';
        else
            out << dist[i] << ' ';

    return 0;
}