#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
FILE *f,*g;
struct per
{
    int nod,gr;
}dumm;
struct muchi
{
    int ini,end,gr;
}puppy;
struct cmp
{
    bool operator() (muchi a,muchi b)
        {
            return a.gr>b.gr;
        }
};

vector<per> veci[50001];
vector<per>::iterator it;
queue<int> usel;
priority_queue<muchi,vector<muchi>,cmp> dijk;
int drum[50001],deg[50001];
bool ok[50001];


int main()
{
    int N,M,i,a,b,c,j;
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    fscanf(f,"%d%d",&N,&M);
    for(i=1;i<=M;i++)
        {
            fscanf(f,"%d%d%d",&a,&b,&c);
            if (b!=1)
            {dumm.nod=b;
            dumm.gr=c;
            veci[a].push_back(dumm);
            deg[b]++;}
        }
    for(i=2;i<=N;i++)
        {
            if (deg[i]==0) {usel.push(i); ok[i]=1;}
        }
    while(!usel.empty())
        {
            i=usel.front();
            usel.pop();
            it=veci[i].begin();
            while(it!=veci[i].end())
                {
                    deg[it->nod]--;
                    if (deg[it->nod]==0) {usel.push(it->nod); ok[it->nod]=1;}
                }
            it++;
        }
    for(i=2;i<=N;i++)
        if (!ok[i]) drum[i]=100000000;
    puppy.ini=1;
    it=veci[1].begin();
    while(it!=veci[1].end())
        {
            puppy.end=it->nod;
            puppy.gr=it->gr;
            dijk.push(puppy);
            it++;
        }
    while(!dijk.empty())
        {
            puppy=dijk.top();
            dijk.pop();
            i=puppy.ini;
            j=puppy.end;
            if (drum[j]>drum[i]+puppy.gr) drum[j]=drum[i]+puppy.gr;
            deg[j]--;
            if (deg[j]==0)
                {
                    puppy.ini=j;
                    it=veci[j].begin();
                    while(it!=veci[j].end())
                        {
                            puppy.end=it->nod;
                            puppy.gr=it->gr;
                            dijk.push(puppy);
                            it++;
                        }

                }
        }
    for(i=2;i<=N;i++)
        {
            fprintf(g,"%d ",drum[i]);
        }













    return 0;
}