#include <bits/stdc++.h>

using namespace std;

#define maxN 50005

struct drum{
    int destinatie,cost;
    drum *next;
};

int main()
{
    ios_base::sync_with_stdio(false);
    ifstream input("dijkstra.in");
    ofstream output("dijkstra.out");

    int n,m;
    input >> n >> m;

    int cost[maxN];
    memset(cost , 127 , sizeof(int)*(n+1) );

    drum *listaNoduri[maxN];




    for(int i=1;i <= m; ++i){
        int x,y,z;
        input >> x >> y >> z;
        drum *temp = new drum;
        *temp = {y,z};
        temp->next = listaNoduri[x];
        listaNoduri[x] = temp;
    }



    int stiva[maxN];
    int index = 0, topLevel = 0;
    cost[1] = 0;


    for( stiva[0] = 1 ; index <= topLevel ; ++index  ){
        int nodCurent = stiva[index];
        drum *temp = listaNoduri[nodCurent];
        for(  ; temp ; temp = temp->next ){
            int nodNou = temp->destinatie;
            int costDeplasare = temp ->cost;
            if(  cost[nodNou] > (cost[nodCurent] +  costDeplasare) ){
                 cost[nodNou] = (cost[nodCurent] +  costDeplasare);
                 stiva[++topLevel] = nodNou;
            }
        }
    }
    int error_value = cost[0];
    for(int i=2;i<=n;++i){
        if( cost[i] == error_value )
            output << "0 ";
        else
            output << cost[i] << " ";
    }


    return 0;
}