#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#define inf 1000000000
using namespace std;
int dmin[50001];
vector <pair <int,int > > g[50001];
class ComparVf
{
public:
    bool operator()(int&x, int&y)
    {
        return dmin[x]>dmin[y];
    }
};
priority_queue <int, vector<int>, ComparVf > coada;
int main()
{
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int n,m,i,a,b,c,nod,x0=1;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++)
        dmin[i]=inf;
    dmin[x0]=0;
    coada.push(x0);
    while(!coada.empty())
    {
        nod=coada.top();
        //cout<<nod<<" ";
        coada.pop();
        for(i=0; i<g[nod].size(); i++)
            if(dmin[g[nod][i].first]>dmin[nod]+g[nod][i].second)
            {
                dmin[g[nod][i].first]=dmin[nod]+g[nod][i].second;
                coada.push(g[nod][i].first);
            }
    }
    for(i=1; i<=n; i++)
    {
        if(i!=x0){
        if(dmin[i]==inf)
            fout<<"0 ";
        else
            fout<<dmin[i]<<" ";
        }
    }
    return 0;
}