#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;
};
vector <graf> lista[NMAX];
priority_queue <int> pq;
int d[NMAX];
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        if(i==1)
            d[i]=0;
        else
            d[i]=-1;
    }
    for(int i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        graf var;
        var.vecin=b;
        var.c=c;
        lista[a].push_back(var);
    }
    pq.push(1);
    while(pq.size()!=0)
    {
        int act=pq.top();
        for(auto x:lista[act])
        {
            int varf=x.vecin;
            int cost=x.c;
            if(varf!=v)
            {
                if(d[varf]==-1)
                {
                    d[varf]=cost+d[act];
                    pq.push(varf);
                }
                else
                {
                    if(d[varf]>d[act]+cost)
                    {
                        d[varf]=d[act]+cost;
                        pq.push(varf);
                    }
                }
            }
        }
        pq.pop();
    }
    for(int i=2;i<=n;++i)
        fout<<d[i]<<" ";
    return 0;
}