#include <bits/stdc++.h>
#define NMAX 50008
#define INF 1000000007

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

struct Muchie
{
    int x, c;
};

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

int n, m, dp[NMAX];
vector <Muchie> G[NMAX];
priority_queue <Muchie, vector<Muchie>, comparare> H;

void Dijkstra();

int main()
{
    ios_base::sync_with_stdio(0); fin.tie(0);
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
    }
    Dijkstra();
    return 0;
}

void Dijkstra()
{
    for (int i = 1; i <= n; i++)
        dp[i] = INF;
    H.push({1, 0});
    dp[1] = 0;

    while (!H.empty())
    {
        int nod = H.top().x;
        int cost = H.top().c;
        H.pop();
        if (cost > dp[nod])
            continue;

        for (auto el : G[nod])
        {
            int x = el.x;
            int c = el.c;
            if (dp[x] > cost + c)
            {
                dp[x] = cost + c;
                H.push({x, dp[x]});
            }
        }
    }

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