#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;
int j,i,n,m,x,y,c;
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[0]=0;
    for(i=1;i<n;i++)
    {
        distanta[i]=1000000;
    }
    for(i=0;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;
            }
    for(i=1;i<n;i++)
    {
        g<<distanta[i]<<" ";
    }
    return 0;
}