#include <bits/stdc++.h>

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

vector<pair<int,int>>graf[50005];
priority_queue<pair<int,int>>q;
int distTo[50005];
int x, y, n, m, c, i;

void Dijkstra(int start, int n, vector<pair<int,int>>graf[], int distTo[])
{
    for(i = 2; i <= n; i++)
        distTo[i] = INT_MAX;

    q.push(make_pair(0, start));

    while(!q.empty())
    {
        int cost = -q.top().first;
        int currentNode = q.top().second;
        q.pop();

        if(cost != distTo[currentNode]) continue;

        for(auto x: graf[currentNode])
            if(distTo[x.second] > cost + x.first)
            {
                distTo[x.second] = cost + x.first;
                q.push(make_pair(-distTo[x.second], x.second));
            }
    }
}
int main()
{
    fin>>n>>m;
    for(i = 1; i <= m; i++)
    {
        fin>>x>>y>>c;
        graf[x].push_back(make_pair(c,y));//v[nod]: pair(cost, vecin)
    }

    Dijkstra(1, n, graf, distTo);

    for(i = 2; i <= n; i++)
    {
        if(distTo[i] == INT_MAX)
            distTo[i] = 0;
        fout<<distTo[i]<<' ';
    }
    return 0;
}