#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
priority_queue <pair <int,int> ,vector <pair <int,int> >, greater <pair <int,int> > > h;
int n,m,i,x,y,cost,nr;
vector <pair <int,int>> v[100005];
int dist[100005],sel[100005];
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        v[x].push_back({y,cost});
    }
    for (i=1;i<=n;i++)
    {
        dist[i] = -1;
    }
    dist[1]=0;
    for (i=0;i<v[1].size();i++)
    {
        int nod = v[1][i].first;
        dist[nod] = v[1][i].second;
        h.push({dist[nod],nod});
    }
    sel[1]=1;
    nr = v[1].size();
    while (nr)
    {
        while (!h.empty()&&sel[h.top().second]==1)
        {
            h.pop();
        }
        pair <int,int> acum = h.top();
        h.pop();
        int nodOr = acum.second;
        sel[nodOr]=1;
        nr--;
        for (int i=0;i<v[nodOr].size();i++)
        {
            int nod = v[nodOr][i].first;
            int costulet = v[nodOr][i].second;
            if (dist[nod]==-1)
            {
                nr++;
                dist[nod] = dist[nodOr]+costulet;
                if (sel[nod]==0)
                {
                    h.push({dist[nod],nod});
                }
            }
            else
            if (dist[nod]>dist[nodOr]+costulet)
            {
                dist[nod] = dist[nodOr]+costulet;
                if (sel[nod]==0)
                {
                    h.push({dist[nod],nod});
                }
            }
        }
    }
    for (i=2;i<=n;i++)
    {
        if (dist[i]==-1)
        {
            dist[i]=0;
        }
        g<<dist[i]<<" ";
    }
    return 0;
}