#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <pair <int,int> > V[50005];
priority_queue < pair <int,int> , vector <pair <int,int> >, greater <pair <int,int> > > pq;
int n,m,dist[50005];
int main()
{
    memset(dist,INF,sizeof(dist));
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        f>>x>>y>>z;
        V[x].push_back(make_pair(y,z));
    }

    dist[1]=0;
    pq.push(make_pair(0,1));

    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        for(int i=0;i<V[u].size();++i)
        {
            int v = V[u][i].first;
            int weight = V[u][i].second;

            if(dist[v]> dist[u]+weight)
            {
                dist[v] = dist[u]+weight;
                pq.push(make_pair(dist[v],v));
            }

        }

    }
    for(int i=2;i<=n;++i)
        if(dist[i]==INF)
            g<<0<<" ";
        else
            g<<dist[i]<<" ";
    return 0;

}