#include <iostream>
#include <fstream>
#include <vector>
#define INF 1000000000
#include <queue>

using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");

struct muchie{
    int nod, cost;
};
vector <muchie> v[50001];
priority_queue < pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > pq; //cost,nod

int d[100000],s[100000];
int main()
{
    int n,p;
    in>>n>>p;
    int x,y,z;
    for( int i=1;i<=p;i++)
    {
        in>>x>>y>>z;
        v[x].push_back({y,z});
    }
    for(int i=1;i<=n;i++) d[i]=INF;
    d[1]=0;
    pq.push({0,1});

    while(!pq.empty())
    {
        int nod = pq.top().second;
        pq.pop();
        if(s[nod]==0)
        {
            s[nod]=1;
            int l=v[nod].size();
            for(int i=0;i<l;i++)
            {
                if(s[v[nod][i].nod]==0)
                if(v[nod][i].cost+d[nod]<d[v[nod][i].nod])
                {
                    d[v[nod][i].nod] = v[nod][i].cost+d[nod];
                    pq.push({ d[v[nod][i].nod], v[nod][i].nod });
                }
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(d[i]!=INF) out<<d[i]<<' ';
        else
            out<<-1<<' ';
    }
    return 0;
}