#include <fstream>
#include <set>
#include <vector>
#include <cstring>
#include <iostream>
#define pb push_back

using namespace std;

const int N = 50005, oo = 1e9;

int n, dist[N];
vector <pair<int, int> > L[N];
vector <pair <int, int> > :: iterator it;
set <pair<int, int> > s;

void Read ()
{
    int m;
    ifstream fin ("dijkstra.in");
    fin >> n >> m;
    int i, x, y, cost;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        L[x].pb({y, cost});
    }
}

void Dijkstra ()
{
    for (int i = 2; i <= n; i++)
        dist[i] = oo;
    s.insert({0, 1});
    while (!s.empty())
    {
        int x = s.begin() -> second;
        int d = s.begin() -> first;
        s.erase(s.begin());
        ///cout << x << " " << d << "\n";
        for (it = L[x].begin(); it != L[x].end(); it++)
            {
                int j = it -> first, k = it -> second;
                if (dist[j] > d + k)
                {
                    if (dist[j] != oo)
                        s.erase(s.find({dist[j], j}));
                    dist[j] = d + k;
                    s.insert({dist[j], j});
                }
            }
    }
    ofstream fout ("dijkstra.out");
    for (int i = 2; i <= n; i++)
    {
        if (dist[i] == oo) dist[i] = 0;
        fout << dist[i] << " ";
    }
}

int main()
{
    Read();
    Dijkstra();
    return 0;
}