#include <iostream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<set<pair<int,int> > > neighbours;
int dist[100005];
void initializeDist(int n)
{
    for(int i=1; i<=n; i++)
        dist[i]=2000000;
}
void bellmanFord(int node,int n)
{
    int hasChanged=1;
    dist[node]=0;
    while(hasChanged!=0)
    {
        hasChanged=0;
        for(int i=1; i<=n; i++)
        {
            set<pair<int,int> > ::iterator eachOne;
            for(eachOne=neighbours[i].begin(); eachOne!=neighbours[i].end(); eachOne++)
                if(dist[(*eachOne).first]>(*eachOne).second+dist[i])
                {
                    dist[(*eachOne).first]=(*eachOne).second+dist[i];
                    hasChanged=1;
                    fout<<(*eachOne).first<<" "<<(*eachOne).second<<"\n";
                }
        }
    }


}
int main()
{
    int n,m;
    fin>>n>>m;
    neighbours=vector<set<pair<int,int> > > (n+1);
    for(int i=0; i<m; i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        neighbours[x].insert({y,cost});
    }
    initializeDist(n);
    bellmanFord(1,n);
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
    return 0;
}