#include <iostream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int dist[100005];
struct graph
{
    int secondNode;
    int cost;
    bool operator<(const graph& otherState) const
    {
        return cost > otherState.cost;
    }
};
vector<vector<pair<int,int> > > neighbours;
void Dijkstra(int node)
{
    dist[node]=0;
    priority_queue<graph>pq;
    pq.push({node,0});
    while(!pq.empty())
    {

        graph currentOne=pq.top();
        pq.pop();
        vector<pair<int,int> > ::iterator neighbour;
        for (neighbour=neighbours[currentOne.secondNode].begin();neighbour!=neighbours[currentOne.secondNode].end();neighbour++)
        {
            int neighbourNode=(*neighbour).first;
            int neighbourCost=(*neighbour).second;
            if(dist[neighbourNode]>dist[currentOne.secondNode]+neighbourCost)
            {
                dist[neighbourNode]=dist[currentOne.secondNode]+neighbourCost;
                pq.push({neighbourNode,dist[neighbourNode]});
            }
        }


    }
}
int main()
{
    int n,m;
    fin>>n>>m;
    neighbours=vector<vector<pair<int,int> > > (n+1);
    for(int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        neighbours[x].push_back({y,cost});
        //neighbours[y].push_back({x,cost});
    }
    for(int i=1;i<=n;i++)
        dist[i]=2000000;
    Dijkstra(1);
    for(int i=2;i<=n;i++)
        if(i!=1 && dist[i]==2000000)
        fout<<"0 ";
        else
        fout<<dist[i]<<" ";
    return 0;
}