#include <iostream>
#include <vector>
#include <fstream>
#include <queue>


using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <int> vec[50005];
vector <int> vec_cost[50005];
priority_queue<pair<int, int>> myheap;
int dist[50005];
int viz[50005];

#define max_size 20000005


int main()
{
    int N, M, x, y, c, i, k, index;
    fin >> N >> M;
    for (i = 1; i <= M; i++)
    {
        fin >> x >> y >> c;
        vec[x].push_back(y);
        vec_cost[x].push_back(c);
    }

    for (i = 1; i <= N; i++) {
        if (i == 1) dist[i] = 0;
        else
            dist[i] = max_size;
        myheap.push(make_pair(-dist[i], i));
    }
    while (!myheap.empty())
    {
        pair<int, int>p = myheap.top();
        index = p.second;
        myheap.pop();
        if (viz[index] == 1);
        else
        {
            viz[index] = 1;

            int lim = vec[index].size();
            for (k = 0; k < lim; k++)
            {
                int vecin = vec[index][k];
                if (dist[vecin] > (dist[index] + vec_cost[index][k]))
                {
                    dist[vecin] = dist[index] + vec_cost[index][k];
                    myheap.push(make_pair(-dist[vecin], vecin));
                }
            }

        }
    }
    for (i = 2; i <= N; i++) {
        if (dist[i] == max_size)
            dist[i] = 0;
        fout << dist[i] << " ";
    }
    return 0;
}