#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define Nmax 50005

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int d[Nmax], n, m;
vector <pair <int, int>> v[Nmax];
struct criteriu
{
    bool operator()(int x, int y)
    {
        if(d[x]!=d[y])
            return d[x]<d[y];
        return x<y;
    }
};
set <int, criteriu> s;
int main()
{
    fin >> n >> m;
    for(int i=2;i<=n;i++)
        d[i]=-1;

    s.insert(1);
    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        v[x].pb(mp(y, c));
    }
    while(!s.empty())
    {
        int u=*s.begin();
        s.erase(s.begin());
        for(auto it:v[u])
            if(d[it.fr]==-1 || (d[it.fr]>d[u]+it.sc))
            {
                if(s.find(it.fr)!=s.end())
                    s.erase(s.find(it.fr));
                d[it.fr]=d[u]+it.sc;
                s.insert(it.fr);
            }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==-1)
            d[i]++;
        fout << d[i] << ' ';
    }
    return 0;
}