#include <bits/stdc++.h>
#define NMAX 50003
#define INF 18446744073709
#define pi pair<unsigned long long, int>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,x,y,c;
struct nod{
    vector<pi> adj;
}v[NMAX];
priority_queue<pi, vector<pi>, greater<pi> > pq;
//dijkstra optim(adica blana)
void dijkstra(int root)
{
    unsigned long long baczaur[NMAX],nod;
    for (int i=2;i<=n;i++)
    {
        baczaur[i]=INF;
    }
    baczaur[root]=0;
    pq.push({0,root});
    while(!pq.empty())
    {
        nod = pq.top().second;
        pq.pop();
        for (unsigned int i=0;i<v[nod].adj.size();i++)
        {
            if (baczaur[v[nod].adj[i].second]>baczaur[nod]+v[nod].adj[i].first)
            {
                baczaur[v[nod].adj[i].second]=baczaur[nod]+v[nod].adj[i].first;
                pq.push({baczaur[v[nod].adj[i].second],v[nod].adj[i].second});
            }
        }
    }
    for (int i=2;i<=n;i++)
    {
        if (baczaur[i]!=INF)
        g<<baczaur[i]<<" ";
        else g<<0<<" ";
    }
}
int main()
{
    f>>n>>m;
    for (int i=0;i<m;i++)
    {
        f>>x>>y>>c;
        v[x].adj.push_back(make_pair(c,y));
    }
    dijkstra(1);
    return 0;
}