using namespace std;
#include <fstream>
#include <vector>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int Nmax=50000;
const int INF=99999999;

struct muchie{int vf, c;} aux;
vector<muchie> vec[Nmax+5];
int dmin[Nmax+5];
bool uz[Nmax+5];

int main()
{
    int i, j, m, n, d, vf, a, b;
    vector<muchie>::iterator it;
    fin>>n>>m;
    for(i=0; i<m; ++i)
    {
        fin>>a>>b>>d;
        aux.vf=b; aux.c=d;
        vec[a].push_back(aux);
    }
    for(i=1; i<=n; ++i) dmin[i]=-1;
    for(it=vec[1].begin(); it!=vec[1].end(); ++it)
        dmin[it->vf]=it->c;

    uz[1]=true;
    for(i=2; i<=n; ++i)
    {//pt fiecare vf ramas
        for(j=1, d=INF; j<=n; ++j)
            if(!uz[j] && dmin[j]>=0)
                if(dmin[j]<d) d=dmin[j], vf=j;
        uz[vf]=1;
        for(it=vec[vf].begin(); it!=vec[vf].end(); ++it)
        {//toti vecinii varfului vf
            if(dmin[it->vf]==-1) dmin[it->vf]=dmin[vf]+(it->c);
            else if(dmin[it->vf]>dmin[vf]+(it->c)) dmin[it->vf]=dmin[vf]+(it->c);
        }
    }
    for(i=2; i<=n; ++i)
        if(dmin[i]==-1) fout<<0<<' ';
        else fout<<dmin[i]<<' ';
    fout<<'\n';
    return 0;
}