#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

#define inf 2100000000

struct nod{int x,t;};
vector<nod> v[501];
vector<nod>::iterator idx,e;

int d[501],dv[501];

struct muchie{int t,a,b;};

class Compare {
public:
    bool operator()(muchie& t1, muchie& t2)
    {
       if (t1.t > t2.t) return true;
       return false;
    }
};

priority_queue<muchie, vector<muchie>, Compare> cd;

int n,m,i,t,a;
nod b;
muchie u;

void add(int s)
{
    int ik=-1;
    e=v[s].end();
    for(idx=v[s].begin();idx!=e;idx++)
    {
        ik++;
        u.a=s;
        u.b=v[s].at(ik).x;
        u.t=v[s].at(ik).t+d[s];
        cd.push(u);
    }
}

void djk(int s)
{
    d[s]=0;
    dv[s]=1;
    add(s);
    while(!cd.empty())
    {
        if(dv[cd.top().b]==0)
        {
            dv[cd.top().b]=1;
            d[cd.top().b]=cd.top().t;
            add(cd.top().b);
        }
        cd.pop();
    }
}

int main()
{
    FILE *f,*g;
    f=fopen("dijkstra.in","rt");
    g=fopen("dijkstra.out","wt");

    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b.x,&b.t);
        v[a].push_back(b);
    }
    fclose(f);

    djk(1);
    for(i=2;i<=n;i++) fprintf(g,"%d ",d[i]);
    fprintf(g,"\n");

    fclose(g);
    return 0;
}