#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n,m,i,j,x,y,d[50005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; //{cost,nod}
struct nod {
int nrv=0;
vector <pair<int, int>> vec; //nod, cost
};
nod c[50005];
int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        d[i]=-1;
    }
    for (i=1; i<=m; i++)
        {
            int val;
            fin>>x>>y>>val;
            c[x].nrv++;
            c[x].vec.push_back({y,val});
        }
    d[1]=0;
    pq.push({0,1});
    while (!pq.empty())
    {
        int val=pq.top().first; //costul pana aici
        int nod=pq.top().second; //nodul
        pq.pop();
        if (val>d[nod]) continue;
        for (i=0;i<c[nod].nrv;i++)
            {
                int nv=c[nod].vec[i].first;
                int cost=c[nod].vec[i].second;
                if (d[nv]==-1 || val+cost<d[nv])
                {
                    d[nv]=val+cost;
                    pq.push({d[nv],nv});
                }
            }
    }
    for (i=2;i<=n;i++) fout<<d[i]<<" ";
    return 0;
}