#include <fstream>
#include <vector>
#include <queue>
#define INF 10000000000LL
using namespace std;
ifstream fi("dijkstra2.in");
ofstream fo("dijkstra2.out");
int n,m,p;
long long D[100001];
int S[100001];
vector <pair<int,int> > ADJ[100001];
vector <pair<int,int> > :: iterator it;
priority_queue <pair<long long, int> > H;
int main()
{
    fi>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        fi>>a>>b>>c;
        ADJ[a].push_back({b,c});
        //ADJ[b].push_back({a,c});
    }
    for (int i=1;i<=n;i++)
        D[i]=INF;
    p=1;
    D[p]=0;
    H.push({0,p});
    while (!H.empty())
    {
        pair <long long,int> P;
        P=H.top();
        H.pop();
        int varf;
        long long cost;
        varf=P.second;
        cost=-P.first;
        if (S[varf]==1)
            continue;
        S[varf]=1;
        for (it=ADJ[varf].begin();it!=ADJ[varf].end();it++)
        {
            pair <int, int> pereche;
            pereche=(*it);
            int vecin,pondere;
            vecin=pereche.first;
            pondere=pereche.second;
            if (cost+pondere<D[vecin])
            {
                D[vecin]=cost+pondere;
                H.push({-D[vecin],vecin});
            }
        }
    }
    for (int i=1;i<=n;i++)
        if (D[i]==INF)
            fo<<-1<<" ";
        else
            fo<<D[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}