#include <iostream>
#include <fstream>
#define inf 1<<30
using namespace std;

ifstream fin("dij.in");
ofstream fout("dij.out");

int n,i,from,m,to,what,d[10000];
struct graf{
    int nod, val;
    graf *urm;
}*L[20];
void add(int from, int to, int what)
{
    graf *p= new graf;
    p->val=what;
    p->nod=to;
    p->urm=L[from];
    L[from]=p;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        if(!d[i])
            d[i]=inf;
        fin>>from>>to>>what;
        if(from==1)
            d[to]=what;
        else
            add(from,to,what);
    }
    for(i=2;i<=n;i++)
    {
        graf *p=L[i];
        while(p)
        {
            if(d[p->nod]>d[i]+p->val)
                d[p->nod]=d[i]+p->val;
           p=p->urm;
        }
    }
    for(i=2;i<=n;i++)
        fout<<d[i]<<' ';
    return 0;
}