#include<bits/stdc++.h>
using namespace std;
# define MAX 1000000
typedef pair<int, int> pereche;
vector<pereche> graf[MAX];
void add( int a,int b, int cost)
{graf[a].push_back(make_pair(b, cost));}
void Disktra(vector<pair<int,int> > graf[], int V, int origine)
{
    priority_queue< pereche, vector <pereche> , greater<pereche> > pq;
    vector<int> dist(V*2, MAX);
    pq.push(make_pair(0, origine));
    dist[origine] = 0;
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        for (auto x : graf[u])
        {
            int v = x.first;
            int cost = x.second;
            if (dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
    for (int i = 1; i <= V; ++i)
        if(dist[i]==MAX)
        cout<<-1<<" ";
    else
       cout<<dist[i]<<" ";

}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int N,p;
    cin>>N>>p;
    int a,b,cost;
   for(int i=2;i<=p;i++){
  cin>>a>>b>>cost;
add(a,b,cost);
   }

    Disktra(graf, N, 1);

    return 0;
}