#include <fstream>
#include <queue>
#include <vector>
#include <iostream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const long long INF = 6000000000;
int n,m,viz[50001];
long long d[50001];
priority_queue < pair < long long, int > > Q;
vector < pair<long long, int> > lista[50001];


int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        lista[x].push_back({c,y});
    }
    viz[1]=1;
    for(int i=2;i<=n;i++)
        d[i]=INF;
    for(auto it:lista[1])
    {
        d[it.second]=it.first;
        Q.push({-d[it.second],it.second});
    }
    while(!Q.empty())
    {
        pair < long long, int > p=Q.top();
        p.first=0-p.first;
        if(viz[p.second]==0)
        {
            viz[p.second]=1;
            for(auto it:lista[p.second])
            {
                if(viz[it.second]==0 && d[p.second]+it.first<d[it.second])
                {
                    d[it.second]=d[p.second]+it.first;
                    Q.push({-d[it.second],it.second});
                }
            }
        }
        Q.pop();
    }
    for(int i=2;i<=n;i++)
        if(d[i]<INF)
            g<<d[i]<<" ";
        else
            g<<0<<" ";
    return 0;
}