#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct graf
{
    int a,b,cost;
}muchie[250005];
int distanta[50005];
int N,M;
bool cmp(int a,int b)
{
    return a<b;
}
int main()
{
    fin>>N>>M;
    distanta[1]=0;
    for(int i=2;i<=N;i++)
    {
        distanta[i]=999999999;
    }
    priority_queue <pair<int,int> > dist;
    for(int i=1;i<=M;i++)
    {
        fin>>muchie[i].a>>muchie[i].b>>muchie[i].cost;
        if(muchie[i].a==1)
        {
            dist.push({muchie[i].cost,muchie[i].b});
            distanta[muchie[i].b]=muchie[i].cost;
        }
    }
    while(!dist.empty())
    {
        for(int i=1;i<=M;i++)
        {
            if(muchie[i].a == dist.top().second && distanta[muchie[i].b]>distanta[muchie[i].a]+muchie[i].cost)
            {
                distanta[muchie[i].b]=distanta[muchie[i].a]+muchie[i].cost;
                dist.push({distanta[muchie[i].b],muchie[i].b});
            }
        }
        dist.pop();
    }
    for(int i=2;i<=N;i++)
    {
        fout<<distanta[i]<<" ";
    }
    return 0;
}