#include <iostream>
#include <fstream>
#define Max 1000001
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int distances[50001];
int n,m;
bool check;

class pairs
{
    int u,v,cost;
public:
    int getU() {return u;}
    int getV() {return v;}
    int getCost() {return cost;}
    void setValues(int U=0,int V=0,int Cost=0) { u=U; v=V; cost=Cost;}
    pairs(int U=0,int V=0,int Cost=0):u(U),v(V),cost(Cost){};
}edges_cost[250001];

void dijkstra()
{
    for(int i=1;i<n;i++) if(distances[i]==0) distances[i]=Max;

    do
    {
        check=false;
        for(int i=0;i<m;i++)
        {
            if(distances[edges_cost[i].getV()]>(distances[edges_cost[i].getU()]+edges_cost[i].getCost()))
               {
                   distances[edges_cost[i].getV()] = distances[edges_cost[i].getU()]+edges_cost[i].getCost();
                   check=true;
               }
        }
    }while(!check);
}

void printDistances()
{
    for(int i=0;i<n;i++)
    {
        if(i==0) continue;
        if(distances[i]<Max) fout << distances[i] << " ";
        else fout << "0 ";
    }
}

int main()
{

    int x,y,tempCost;
    fin >> n >> m;

    for(int i=0;i<m;i++)
    {
        fin >> x >> y >> tempCost;
        x--; y--;
        edges_cost[i].setValues(x,y,tempCost);
        if(x==0) distances[y]=tempCost;

    }

    dijkstra();
    printDistances();

    return 0;
}