#include <bits/stdc++.h>
#define infinit 1000000001

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijsktra.out");

struct muchie
{
    int nod,cost;
};


priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
vector <muchie> a[100001];
int viz[100001],d[100001],n;

void dijkstra(int s)
{
    int nod,cost,i,k,pmin;
    for(i=0;i<=n;i++)
    {
        d[i]=infinit;
    }
    d[s]=0;
    pq.push({0,s});
    while(!pq.empty())
    {
        pmin=pq.top().second;
        pq.pop();
        if(viz[pmin]==0)
        {
            viz[pmin]=1;
            for(i=0;i<a[pmin].size();i++)
            {
                nod=a[pmin][i].nod;
                cost=a[pmin][i].cost;
                if(d[nod]>d[pmin]+cost)
                {
                    d[nod]=d[pmin]+cost;
                    pq.push({d[nod],nod});
                }
            }
        }
    }
}

int main()
{int m,i,j,x,y,nr=0,s,cost;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        a[x].push_back({y,cost});
    }
    s=1;
    dijkstra(s);
    for(i=2;i<=n;i++)
    {
        if(d[i]==infinit)
        {
            d[i]=-1;
        }
        g<<d[i]<<" ";
    }
    return 0;
}