#include <bits/stdc++.h>
#define NMAX 50000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,v,a,b,c;
struct graf
{
    int vecin;
    int c;
};
struct cost
{
    int varf;
    int dist;

    bool operator<(const cost &other) const{
        return this->dist >other.dist;
    }
};
vector <graf> lista[NMAX];
priority_queue <cost> pq;
int d[NMAX];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        graf var;
        var.vecin=b;
        var.c=c;
        lista[a].push_back(var);
    }
    for(int i=1;i<=n;++i)
    {
        if(i==1)
            d[i]=0;
        else
            d[i]=-1;
    }
    cost var;
    var.varf=1;
    var.dist=0;
    pq.push(var);
    while(pq.size()!=0)
    {
        cost var=pq.top();
        int v=var.varf;
        int c=var.dist;
        for(auto x:lista[v])
        {
            if(d[x.vecin]==-1 || (d[x.vecin]!=-1 && d[x.vecin]>d[v]+x.c))
            {
                d[x.vecin]=d[v]+x.c;
                cost adaugare;
                adaugare.varf=x.vecin;
                adaugare.dist=d[v]+x.c;
                pq.push(adaugare);
            }
        }
        pq.pop();
    }
    for(int i=2;i<=n;++i)
        fout<<d[i]<<" ";
    return 0;
}