#include <bits/stdc++.h>

#define MAX 50000

using namespace std;

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

struct node
{
    int x, cost;
    bool operator < (const node & a) const
    {
        if(a.cost != cost)
            return cost > a.cost;
        return x > a.x;
    }
};


int n, m, dp[MAX + 5], a, b, c;
vector <pair<int,int>> v[MAX + 5];

void dij(int x)
{
    for(int i = 1;i <= n; ++i)
        if(i != x) dp[i] = 1e9;
    dp[x] = 0;

    priority_queue<node> pq;
    pq.push({x, 0});
    while(!pq.empty())
    {
        node curr = pq.top();
        pq.pop();

        if(curr.cost != dp[curr.x])
            continue;

        for(auto i : v[curr.x])
        {
            if(dp[i.first] > curr.cost + i.second)
            {
                dp[i.first] = curr.cost + i.second;
                pq.push({i.first, dp[i.first]});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1;i <= m; ++i)
    {
        fin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    dij(1);
    for(int i = 2;i <= n; ++i)
        fout << (dp[i] == 1e9 ? 0 : dp[i]) << ' ';
}