#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct t
{
    int nod,dist;
};
vector <t>v[50005];
queue<int>q;
int i,n,m,a,b,c,dist[50005],inf,nod;
int main()
{
    fin>>n>>m;
    inf=250005;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    for(i=1; i<=n; i++)
        dist[i]=inf;
    dist[1]=0;
    q.push(1);
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        viz[nod]=0;
        for(auto it:v[nod])
            if(dist[it.nod]>dist[nod]+it.dist)
            {
                dist[it.nod]=dist[nod]+it.dist;
                q.push(it.nod);
                if(!viz[it.nod])
                    viz[it.nod]=1;
            }
    }
    for(int i=2; i<=n; i++)
        if(dist[i]==inf)
            fout<<0<<' ';
        else fout<<dist[i]<<' ';
    return 0;
}