#include <bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int N=50005,inf=1e9;
int n,m,x,y,z;
vector<PII> v[N];
priority_queue<pair<int,int>> q;
int d[N],f[N];
void DIJ(int nd)
{
    q.push({0,nd});
    while(q.size())
    {
        int c,a;
        tie(c,a)=q.top();
        c=-c;
        q.pop();
        if(f[a])continue;
        f[a]=1;
        for(auto it:v[a])
        {
            if(d[it.first]>c+it.second)
            {
                d[it.first]=c+it.second;
                q.push({-d[it.first],it.first});
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(i!=nd)
        {
            if(d[i]==inf)
                d[i]=-1;
            fout<<d[i]<<" ";
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(int i=1; i<=n; i++)
        d[i]=inf;
    DIJ(1);
    return 0;
}