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

using namespace std;

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

#define NMAX 50005
#define INF 1000000000

int n, m;
vector<pair<int, int>> G[NMAX];
int d[NMAX];
bitset<NMAX> viz;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;

void citire() {
    f >> n >> m;
    int nod1, nod2, cost;
    for (int i = 0; i < m; i++) {
        f >> nod1 >> nod2 >> cost;
        G[nod1].push_back({cost, nod2});
    }
}

void initializare()
{
    for (int i = 1; i <= n; i++)
        d[i] = INF;
}

void parcurgere()
{
    d[1]=0;
    int vf = 1;
    q.push({0,1});
    while (!q.empty())
        {
        vf = q.top().second;

        q.pop();

        if(viz[vf])
            continue;

        viz[vf] = true;

        for (auto &nod:G[vf])
            if (d[vf] + nod.first < d[nod.second])
            {
                d[nod.second] = d[vf] + nod.first;
                q.push({d[nod.second], nod.second});
            }

    }
}

void afisare() {
    for (int i = 2; i <= n; i++) {
        if (d[i] == INF)
            g << 0 << ' ';
        else
           g << d[i] << ' ';
    }
}

int main() {
    citire();
    initializare();
    parcurgere();
    afisare();
    return 0;
}