#include <bits/stdc++.h>

using namespace std;
#define per pair<int,int>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int N=50001;
priority_queue<per> pq;
vector<per> v[N];
int dist[N];
int main()
{
    int p,n,i,x,y,z,nod,m,nod2,cost;
    fin>>n>>m;
    while(fin>>x>>y>>z){
        v[x].push_back({-z,y});
    }
    for(i=1;i<=n;i++)
        dist[i]=INT_MAX;
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty())
    {
        nod=pq.top().second;
        pq.pop();
        m=v[nod].size();
        for(i=0;i<m;i++)
        {
            cost=-v[nod][i].first;
            nod2=v[nod][i].second;
            if(dist[nod2]>dist[nod]+cost)
            {
                dist[nod2]=dist[nod]+cost;
                pq.push({dist[nod2],nod2});
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]==INT_MAX)
            fout<<"-1 ";
        else
            fout<<dist[i]<<" ";
    }
    return 0;
}