#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <climits>
#define INF INT_MAX

using namespace std;

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

int n, m, x, y, c, d[100010];

struct muchie
{
    int vf, cost;
};

vector<muchie> v[50010];

int main()
{
    f>>n>>m;
    for (int i = 1; i <= m; i++)
    {
        f>>x>>y>>c;
        v[x].push_back({y, c});
    }
    for (int i = 0; i <= n + 1; i++)
        d[i] = INF;
    int init = 1;
    d[init] = 0;
    int l = v[init].size();
    set<pair<int, int> > heap;
    heap.insert({0, init});
    while(!heap.empty())
    {
        pair<int, int> tmp = *(heap.begin());
        heap.erase(heap.begin());
        int u = tmp.second;
        l = v[u].size();
        for (int i = 0; i < l; i++)
        {
            int vc = v[u][i].vf;
            int dist = v[u][i].cost;
            if (d[u] + dist < d[vc])
            {
                if (d[vc] != INF)
                    heap.erase(heap.find({d[vc], vc}));
                d[vc] = d[u] + dist;
                heap.insert({d[vc], vc});
            }
        }
    }
    for (int i = 2; i <= n; i++)
        if (d[i] != INF)
            g<<d[i]<<" ";
        else
            g<<0<<" ";
    return 0;
}