#include <fstream>
#include <vector>

using namespace std;

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


struct abc
{
    int unde;
    int cost;
};

vector<abc> vecini[50005];
abc aux;
bool a;
int j,i,n,m,x,y,c,k;
int distanta[50005],predecesor[50005];

int main()
{
    f>>n>>m;
    for(i=0; i<m; i++)
    {
        f>>x>>y>>c;
        aux.unde=y;
        aux.cost=c;
        vecini[x].push_back(aux);
    }
    distanta[1]=0;
    for(i=2; i<=n; i++)
    {
        distanta[i]=1000000;
    }
    a=true;
    while(a){
    a=false;
    for(i=1; i<=n; i++)
        for(j=0; j<vecini[i].size(); j++)
            if(distanta[i]+vecini[i][j].cost<distanta[vecini[i][j].unde])
            {
                distanta[vecini[i][j].unde]=distanta[i]+vecini[i][j].cost;
                predecesor[vecini[i][j].unde]=i;
                a=true;
            }
    }
    for (i = 2; i <= n; i++)
    {
        if (distanta[i] == 1000000)
            g<< "0 ";
        else
            g<< distanta[i] << ' ';
    }
    return 0;
}