#include <bits/stdc++.h>

#define MAXN 50007
#define INF 20010

using namespace std;

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

int n, m, d[MAXN];
vector<pair<int, int> > adj[MAXN];
set<pair<int, int> > q;

void dij()
{
    for(int i = 2; i <= n; i++)
        d[i] = INF;
    q.insert({0, 1});
    while(!q.empty())
    {
        pair<int, int> crt = *q.begin();
        q.erase(q.begin());
        for(auto& it: adj[crt.second])
        {
            if(d[it.second] > d[crt.second] + it.first)
            {
                if(d[it.second] != INF) q.erase(q.find({d[it.second], it.second}));
                d[it.second] = d[crt.second] + it.first;
                q.insert({d[it.second], it.second});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        adj[x].push_back({c, y});
    }
    dij();
    for(int i = 2; i <= n; i++)
        fout << d[i] << " ";

    return 0;
}