#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n, m;
int imax = numeric_limits<int>::max();
const int nmax=1e5;
struct compare
{
    bool operator()(int p, int q)
    {
        return p > q;
    }
};
int d[nmax];
vector <int> sol;

vector <pair<int, int> > v[nmax];
priority_queue<int, vector<int>, compare> q;
bitset <nmax> fr;
void DIJ(int start)
{
    for(int i=1;i<=n;i++)
    {
        d[i]=imax;
    }
    d[1]=0;
    fr[1]=1;
    q.push(1);
    while(q.size())
    {
        int curent = q.top();
        int vecin, cost;
        q.pop();
        for(int i=0;i<v[curent].size();i++)
        {
            vecin = v[curent][i].first;
            cost = v[curent][i].second;

                if(d[curent] + cost < d[vecin])
                {
                    d[vecin] = d[curent] + cost;
                    if(!fr[vecin])
                {
                    fr[vecin]=true;
                    q.push(vecin);
                }
                }


        }
    }
}
int main()
{


    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        if(i<=n)
        {
            d[i]=-1;
        }
        int x, y, cost;
        in>>x>>y>>cost;
        v[x].push_back({y, cost});
    }
    DIJ(1);
    for(int i=2;i<=n;i++)
    {
        if(d[i]==imax)
        {
            out<<"-1 ";
        }
        else
        {
            out<<d[i]<<' ';
        }
    }
    return 0;
}