#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 );

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 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