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

using namespace std;

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

int distanta[50005];
bool in_coada[50005];
vector <pair <int, int> > G[50005];
queue <int> coada;

int main()
{
    int n,m,i,j,k,a,b,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;i++)
        distanta[i]=1<<30;
    distanta[1]=0;
    coada.push(1);
    in_coada[1]=1;
    while(coada.empty()==0)
    {
        int nod=coada.front();
            for(k=0;k<G[nod].size();k++)
                if(distanta[nod]+G[nod][k].second<distanta[G[nod][k].first])
                {
                    distanta[G[nod][k].first]=distanta[nod]+G[nod][k].second;
                    if(in_coada[G[nod][k].first]==0)
                    {
                        coada.push(G[nod][k].first);
                        in_coada[G[nod][k].first]=1;
                    }
                }
        coada.pop();
    }
    for(i=2;i<=n;i++)
        if(distanta[i]!=1<<30)
            g<<distanta[i]<<' ';
        else g<<"0 ";
    return 0;
}