#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

struct Edge
{
    int nod, cost;
};

int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int n, m;
    fin >> n >> m;
    vector<int> d(n + 1, (n - 1) * 20000), viz(n + 1, 0);
    vector<vector<Edge>> G(n + 1);
    set<pair<int, int>> s;
    d[1] = 0;
    s.insert(make_pair(0, 1));
    for (int i = 0; i < m; i++)
    {
        int a, b, cost;
        Edge k;
        fin >> a >> b >> cost;
        k.nod = b;
        k.cost = cost;
        G[a].push_back(k);
    }
    for (int i = 1; i <= n; i++)
    {
        if (s.empty())
            break;
        int ind = (*s.begin()).second;
        s.erase(s.begin());
        for (auto edge: G[ind])
        {
            if (d[edge.nod] > d[ind] + edge.cost)
            {
                s.erase(make_pair(d[edge.nod], edge.nod));
                d[edge.nod] = d[ind] + edge.cost;
                s.insert(make_pair(d[edge.nod], edge.nod));
            }
        }

    }

    for (int i = 2; i <= n; i++)
    {
        if (d[i] == (n - 1) * 20000)
            fout << 0 << " ";
        else
            fout << d[i] << " ";

    }

    return 0;
}