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

vector<per> veci[50001];
vector<per>::iterator it;
priority_queue<muchi,vector<muchi>,cmp> dijk;
int drum[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);
            }
        }
    for(i=2;i<=N;i++) drum[i]=100000000;
    puppy.nod=1;
    puppy.gr=0;
    dijk.push(puppy);
    while(!dijk.empty())
        {
            puppy=dijk.top();
            dijk.pop();
            i=puppy.nod;
            j=puppy.gr;
            if (j==drum[i])
                {
                    it=veci[i].begin();
                    while(it!=veci[i].end())
                        {
                            if (j+it->gr<drum[it->nod]) {drum[it->nod]=j+it->gr;puppy.nod=it->nod;puppy.gr=drum[it->nod];dijk.push(puppy);}
                            it++;

                        }
                }

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













    return 0;
}