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

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

struct Muchie
{
    int nod, cost;
};

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

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

void Dijkstra(int start);

int main()
{
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
    }

    for (int i = 1; i <= n; i++)
        dp[i] = INF;

    Dijkstra(1);
    for (int i = 2; i <= n; i++)
        fout << dp[i] << ' ';
    return 0;
}

void Dijkstra(int start)
{
    Muchie M;
    dp[start] = 0;
    H.push({start, dp[start]});

    while (!H.empty())
    {
        M = H.top();
        H.pop();

        for (auto el : G[M.nod])
        {
            int vecin = el.first;
            int c = el.second;
            if (M.cost + c < dp[vecin])
            {
                dp[vecin] = M.cost + c;
                H.push({vecin, dp[vecin]});
            }
        }

    }
}