#include <bits/stdc++.h>

using namespace std;

#define TITLE "dijkstra"
ifstream f (TITLE".in");
ofstream g (TITLE".out");

bitset<50003> Visited;

void Dijkstra(int StartNode, vector<vector<pair<int,int>>> &Graph, vector<long long int> &Distante)
{
    Distante[StartNode]=0;
    priority_queue<pair<int,int>> PQ;
    PQ.push({0, StartNode});
    for(;!PQ.empty(); PQ.pop())
    {
        int CurrentNode=PQ.top().second;
        if(!Visited[CurrentNode])
        {
            Visited[CurrentNode]=true;
            for(auto it : Graph[CurrentNode])
            {
                if(Distante[CurrentNode]+it.second<Distante[it.first])
                {
                    Distante[it.first]=Distante[CurrentNode]+it.second;
                    PQ.push({-Distante[it.first],it.first});
                }
            }
        }
    }
}

int main()
{
    int n,m;
    f>>n>>m;
    vector<vector<pair<int,int>>> Graph(n+1);
    for(int a,b,c; f>>a>>b>>c; Graph[a].push_back({b,c}));
    vector<long long int> Distante(n+1,INT_MAX);
    Dijkstra(1,Graph,Distante);
    for(int i=2; i<=n; i++)
    {
        if(Distante[i]==INT_MAX)
            g<<0<<' ';
        else
            g<<Distante[i]<<' ';
    }
    return 0;
}