#include <bits/stdc++.h>


using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

queue <int> q;
vector <pair<int,int>> graf[50001];

int n,m, d[50001], viz[50001];

void citire() {
    int x,y,c;
    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y,c});
        //graf[y].push_back({x,c});
    }
    for (int i=1;i<=n;i++){
        d[i]=-1;
    }
}

void alg(){
    int nod;
    q.push(1);
    nod=1;
    d[1]=0;
    while (!q.empty())
    {
        q.pop();
        viz[nod]++;
        if (viz[nod]<=n)
        {
            for (pair<int,int> el: graf[nod])
            {
                if (d[el.first]==-1 || d[el.first]>d[nod]+el.second)
                {
                    d[el.first]=d[nod]+el.second;
                    q.push(el.first);
                }
            }
        }
        nod=q.front();
    }
}

int main()
{
    citire();
    alg();
    for (int i=2;i<=n;i++) {
        if (d[i]!=-1)fout << d[i] << " ";
        else fout << 0 << " ";
    }
}