/*
    Algoritmul lui Dijkstra
*/
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define MAXN 50005
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define PlusINFINITY ((1LL<<31)-1)

using namespace std;

vector<int> V[MAXN];
vector<int> C[MAXN];

queue<int> Queue;
int distMin[MAXN];
bitset<MAXN> inQueue( 0 );

//MAXN = 5
//inQueue: 00000
//00000000000000000000000000000000000000000000000

int nodes,
    edges;

void read_graph() {
    int x,
        y,
        cost;

    freopen(FIN, "r", stdin);

    scanf("%d %d", &nodes, &edges);
   // printf("%d %d\n", nodes, edges);

    for(int edge = 1; edge <= edges; ++edge) {
        //3 5 6
        //x = 3
        //y = 5
        //cost = 6
        //V[ 3 ].push_back( 5 );
        //C[ 3 ].push_back( 6 );
        scanf("%d %d %d", &x, &y, &cost);
        printf("%d %d %d\n", x, y, cost);

        V[ x ].push_back( y );
        C[ x ].push_back(cost);
    }
}

void display_graph() {
    
    printf("Graful reprezentat prin lista de adiacenta: \n");

    for(int i = 1; i <= nodes; ++i) {
    
        printf("Node %d --->", i);

        for(int j = 0; j < V[i].size(); ++j)
            cout<<V[i][j]<<" ";
        printf("\n");
    }
}

void display_costs() {
    
    printf("Graful costurilor: \n");

    for(int i = 1; i <= nodes; ++i) {

        printf("Node %d --->", i);

        for(int j = 0; j < V[i].size(); ++j)
            cout<<C[i][j]<<" ";
        printf("\n");
    }
} 

/*
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6

V[1].size() => 2

V[1][0] -> 2
V[1][1] -> 4

Listele de adiacenta:
1: 2, 4
2: 3
3: 5
4: 5
5: NULL

facem o asociere intre V[nodes] si C[nodes]

Costuri:
1: 1, 2
2: 2
3: 6
4: 3
5: NULL

C[3][0] =>

V[2].size() = 1
V[2][0] --->2
C[2][0] ->>2


*/

// ---> 1 2 3 4 5 6 7 8 9 10 11 <---
//int curr = Queue.front()
//curr = 1
//Queue.push(11)

//distMin[i] = distanta de la nodul 1 la i, unde i reprezinta un nod de la 2, la nodes

//tehnica Greedy
void dijkstra() {

    for(int i = 2; i <= nodes; ++i) distMin[ i ] = PlusINFINITY;

    distMin[1] = 0;

    Queue.push( 1 );
    
    inQueue[ 1 ] = true;

    while( !Queue.empty() ) {
        
        int curr = Queue.front();

        Queue.pop();

        inQueue[ curr ] = false;

        for(int i = 0; i < V[ curr ].size(); ++i) {

            int y = V[ curr ][i];
            int cost = C[ curr ][i];
            
            if( distMin[y] > distMin[ curr ] + cost ) {
                
                distMin[ y ] = distMin[ curr ] + cost;

                if(!inQueue[ y ]) {
                    
                    Queue.push( y );
                    inQueue[ y ] = true;
                }
            }
        }
    }
}

void write_data() {
    
    freopen(FOUT, "w", stdout);
    printf("Dijkstra in action:\n");
    for(int i = 2; i <=nodes; i++)  printf("%d ", (distMin[ i ] < PlusINFINITY) ? distMin[ i ] : 0);
}

int main()
{
    read_graph();
  //  display_graph();
  //  display_costs();
    dijkstra();
    write_data();
}