/*
Author: Plamen Nachev
Algorithm of Floyd-Warshall on unoriented graph.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e+2;
const int MAX_VALUE = 1e+9;
int N, M;
int dist[MAXN][MAXN], next[MAXN][MAXN];

void input()
{
    scanf("%d %d", &N, &M);
    memset(dist, 63, sizeof(dist));
    memset(next, -1, sizeof(next));

    int first, second, price;
    for( int i = 0; i < M; i++ )
    {
        scanf("%d %d %d", &first, &second, &price);
        dist[first-1][second-1] = dist[second-1][first-1] = price;
        next[first-1][second-1] = second-1;
        next[second-1][first-1] = first-1;
    }
}

void floyd()
{
    for( int k = 0; k < N; k++ )
    for( int i = 0; i < N; i++ )
    for( int j = 0; j < N; j++ )
    if( dist[i][j] > dist[i][k] + dist[k][j] )
    {
        dist[i][j] = dist[i][k] + dist[k][j];
        next[i][j] = next[i][k];
    }

    for( int i = 0; i < N; i++ )
        dist[i][i] = 0;

    printf("Minimal distances between all two pairs of vertices:\n");
    for( int i = 0; i < N; i++ )
    {
        for( int j = 0; j < N; j++ )
            printf("%d ", dist[i][j]);
        printf("\n");
    }

    int start = 2, end = 4; /// example vertices
    printf("Minimal distance between (example) vertices %d and %d is: %d\n", start+1, end+1, dist[start][end]);
    printf("Path is: \n");

    while( start != end )
    {
        printf("%d ", start+1);
        start = next[start][end];
    }
    printf("%d\n", end+1);
}

int main()
{
    input();
    floyd();

    return 0;
}
/**
Example(input):
5 7
1 2 1
1 3 5
3 2 2
2 4 6
4 3 1
5 2 2
4 5 1
**/