#include <iostream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int dist[50005];

struct node{
int firstNode;
int secondNode;
int cost;
};
vector<node > muchii;
vector<set<int> > neighbours;
void bfs(int node)
{
    queue <int> theQueue;
    theQueue.push(node);
    while(!theQueue.empty())
    {
        int currentNode=theQueue.front();
        theQueue.pop();
        set<int> ::iterator eachOne;
        for(eachOne=neighbours[currentNode].begin(); eachOne!=neighbours[currentNode].end(); eachOne++)
        {

            for(int i=0; i<muchii.size(); i++)
            {
                if(muchii[i].secondNode== *eachOne && muchii[i].firstNode== currentNode)
                    if(dist[currentNode]+muchii[i].cost<dist[*eachOne])
                    {

                        dist[*eachOne]=dist[currentNode]+muchii[i].cost;
                        theQueue.push(*eachOne);

                    }

            }


        }

    }
}
int main()
{
    int n,p,m;
    //pbinfo:
    //fin>>n>>p;
    fin>>n>>m;
    neighbours=vector<set<int> > (n+1);
    int x,y,cost;
    //pbinfo
    //while(fin>>x>>y>>cost)
    for(int i=0;i<m;i++)
    {
        //infoarena
        fin>>x>>y>>cost;
        muchii.push_back({x,y,cost});
        neighbours[x].insert(y);
    }
    for(int i=1; i<=n; i++)
        dist[i]=2000000;
    dist[1]=0;
    bfs(1);

    for(int i=2;i<=n;i++)
        if(dist[i]==2000000)
        fout<<"0"<<" ";
        else
        fout<<dist[i]<<" ";
    return 0;
}