#include <bits/stdc++.h>
#define INF 1000000004
#define NMAX 50004

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

struct Muchie
{
    int nod, cost;
    friend bool operator>(const Muchie &, const Muchie &);
};

bool operator >(const Muchie & a, const Muchie & b)
{
    return a.cost > b.cost;
}

priority_queue <Muchie, vector <Muchie>, greater<Muchie> > H;

int n, m, start;
int dp[NMAX], viz[NMAX];
vector < pair <int, int> > G[NMAX];

void citire();
void Dijkstra();

int main()
{
    citire();
    Dijkstra();
    for (int i = 2; i <= n; i++)
    {
        if (dp[i] == INF)
            fout << 0;
        else
        {
            fout << dp[i];
        }
        fout << ' ';
    }
    return 0;
}

void citire()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }
    for (int i = 0; i <= n; i++)
        dp[i] = INF;
}

void Dijkstra()
{
    Muchie M;
    M.nod = 1;
    M.cost = 0;
    H.push(M);
    dp[1] = 0;

    while (!H.empty())
    {
        M = H.top();
        H.pop();
        if (viz[M.nod])
            continue;
        viz[M.nod] = 1;

        for (int i = 0; i < G[M.nod].size(); i++)
        {
            int vf = G[M.nod][i].first;
            int cost = G[M.nod][i].second;
            if (dp[vf] > dp[M.nod] + cost)
            {
                dp[vf] = dp[M.nod] + cost;
                H.push({vf, dp[vf]});
            }
        }
    }
}