#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;

vector < pair < int, int >> vecini[NMAX];
priority_queue < pair < int, int >> dist_mini;
int dist_noduri[NMAX];

int n, m;

void Dijkstra(int nod)
{
    dist_noduri[nod] = 0;
    dist_mini.push({-dist_noduri[nod], nod});
    while(!dist_mini.empty())
    {
        int nod_curent = dist_mini.top().second;
        int distanta = -dist_mini.top().first;
        dist_mini.pop();

        if (distanta != dist_noduri[nod_curent])
            continue;

        for (int i = 0; i < vecini[nod_curent].size(); ++i)
        {
            if (dist_noduri[vecini[nod_curent][i].first] <= dist_noduri[nod_curent] + vecini[nod_curent][i].second)
                continue;
            dist_noduri[vecini[nod_curent][i].first] = dist_noduri[nod_curent] + vecini[nod_curent][i].second;
            dist_mini.push({ -dist_noduri[vecini[nod_curent][i].first], vecini[nod_curent][i].first});
        }
    }

     for(int i=2; i<=n; ++i)
        {
            if(dist_noduri[i] == 100000000)
                dist_noduri[i] = 0;
            fout << dist_noduri[i] << " ";
        }
}

int main()
{
    fin >> n >> m;

    for(int i=1; i<=n; ++i)
        dist_noduri[i] = 100000000;

    for(int i=1; i<=m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        vecini[x].push_back({y, cost});
    }

    Dijkstra(1);
    return 0;
}