#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax=10000;
const int INF=1<<30;
int a[nmax][nmax];
vector <int> d(nmax,INF);
bool viz[nmax];
int x,y,c;
int main()
{
    int n,m;
    fin>>n>>m;
    while(fin>>x>>y>>c)
    {
        a[x][y]=c;
        if(x==1)
            d[y]=c;
    }
    d[1]=0;
    viz[1]=1;
    for(int k=1; k<=n; ++k)
    {
        int pmin=INF;
        for(int i=1; i<=n; ++i)
        {
            if(!viz[i] && d[i]<pmin)
                pmin=i;
        }
        if(pmin!=INF)
        {
            viz[pmin]=1;
            for(int j=1; j<=n; ++j)
            {
                if(!viz[j] && a[pmin][j]>0 && d[j]>d[pmin]+a[pmin][j])
                    d[j]=d[pmin]+a[pmin][j];
            }
        }
    }
    for(int i=2; i<=n; ++i)
        if(d[i]!=INF)
            fout<<d[i]<<" ";
        else
            fout<<-1<<" ";
}