#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define mx 50001
#define inf INT_MAX

using namespace std;

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

int n, m, d[mx];
vector < pair<int,int> > v[mx];
priority_queue < pair<int,int> > q;

void citire()
{
    fin>>n>>m;
    int x, y, cost;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    fin.close();
}

void dijkstra(int poz)
{
    for(int i=1;i<=n;i++)
        d[i]=inf;
    d[1]=0;
    q.push({0,1});
    int curent, cost, vecin;
    while(!q.empty())
    {
        curent=q.top().second;
        cost=-q.top().first;
        q.pop();
        if(d[curent]==cost)
        {
            for(int i=0;i<v[curent].size();i++)
            {
                vecin=v[curent][i].first;
                if(d[curent]+v[curent][i].second<d[vecin])
                {
                    d[vecin]=d[curent]+v[curent][i].second;
                    q.push({-d[vecin],vecin});
                }
            }
        }
    }
}

void afisare()
{
    for(int i=2;i<=n;i++)
    {
        if(d[i]==inf)
            fout<<-1<<' ';
        else
            fout<<d[i]<<' ';
    }
    fout.close();
}

int main()
{
    citire();
    dijkstra(1);
    afisare();
    return 0;
}