/*
     Algoritmul lui Dijkstra
*/
#include <bits/stdc++.h>
#include <vector>
#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 liste 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];//2

              int cost = C[ curr ][i];//1
                                            1
              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(int argc, char const *argv[]) {

  read_graph();
  dijkstra();
  write_data();
  return 0;
}

//Microsoft Access = sistem de gestiune al bazelor de date
//Oracle