#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 q=1;
    while( (d[H[q]] > d[H[q*2]] && q*2<=hp) || (d[H[q]] > d[H[q*2+1]] && q*2+1<=hp) )
    {
        if((d[H[q]] > d[H[q*2]] && q*2<=hp) && (d[H[q*2]] < d[H[q*2+1]] || q*2+1>hp) )
        {
            swap(H[q], H[q*2]);
            q=q*2;
        }
        else if(d[H[q]] > d[H[q*2+1]] && 2*q+1 <= hp)
        {
            swap(H[q],H[q*2+1]);
            q=q*2+1;
        }
    }
}

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;
}