/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define inf 2000001
#define cin fin
#define cout fout
vector <vector <pair <int, int> > > a;
vector <int> drum;
vector <bool> viz;
int n,m,p;
void dijk(int x)
{
    viz[x]=1;
    for(pair <int,int> i : a[x])
    {
        if(drum[x]+i.second<drum[i.first])
        {
            drum[i.first]=drum[x]+i.second;
        }
    }
    int mini=inf,nod,ok=0;
    for(int i=1;i<=n;i++)
    {
        if(drum[i]<mini && viz[i]==0)
        {
            mini=drum[i];
            nod=i;
            ok=1;
        }
    }
    if(ok)
    dijk(nod);
}
int main()
{
    cin >> n >> m;
    a.resize(n+1);
    drum.resize(n+1,inf);
    viz.resize(n+1,0);
    int x,y,z;
    while(fin >> x && fin >> y && fin >> z)
    {
        a[x].push_back({y,z});
    }
    drum[1]=0;
    dijk(1);
    for(int i=2;i<=n;i++)
    if(drum[i]!=inf)
    cout << drum[i] << ' ';
    else
    cout << "-1" << ' ';
    return 0;
}