#include <fstream>
#include <list>
#define DIM 500001

using namespace std;
int n,m,x,y,c,H[DIM],d[DIM],hp;
bool v[DIM];

list<pair<int,int> > nod[DIM];

void addHeap(int k)
{
    H[++hp]=k;
    int q=hp;
    while(d[H[q]]<d[H[q/2]] && q>1)
    {
        swap(H[q],H[q/2]);
        q=q/2;
    }
}
void delHeap(int k)
{
    H[k]=H[hp];
    --hp;

    int son;
    do{
        son=0;
        if(k*2 <=hp){
            son=k*2;
            if( k*2+1 <= n && d[H[k*2]]>d[H[k*2+1]] ){
                son=k*2+1;
            }
            if(d[H[son]] >= d[H[k]]){
                son=0;
            }

        }
        if(son) {
            swap(H[k] , H[son]);
            k=son;
        }
    }while(son);
}

void dijkstra(int k)
{
    addHeap(k);
    while(hp!=0)
    {
        int vf=H[1];
        delHeap(1);
        for(list<pair<int,int> >::iterator i=nod[vf].begin();i!=nod[vf].end();++i)
        {
            std::pair<int,int> z=*i;
            if(!v[z.first])
            {
                d[z.first]=d[vf]+z.second;
                v[z.first]=1;
                addHeap(z.first);
            }
        }
    }
}

int main()
{
    FILE *f=fopen("dijkstra.in","r");
    FILE *g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",  &n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d", &x,&y,&c);
        nod[x].push_back(make_pair(y,c));
    }
    dijkstra(1);
    for(int i=2;i<=n;++i)
        fprintf(g,"%d ",d[i]);
    fprintf(g,"\n");
    fclose(f);
    fclose(g);
    return 0;
}