#include<iostream>

#include<algorithm>

using namespace std;

const int maxint = ;

const int maxn = ;

int x, y, z;

int dis[maxn][maxn];

int n, m;

void floyd() {

    for (int k = ; k <= n; ++k) {   //枚举中间点k

        for (int i = ; i <= n; ++i) {   //枚举端点i

            for (int j = ; j <= n; ++j) {   //枚举端点j

                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

            }

        }

    }

}

int main() {

    while (cin >> n >> m&&n&&m) {

        for (int i = ; i <= n; ++i) {

            for (int j = ; j <= n; ++j) {

                dis[i][j] = maxint;

            }

        }

        for (int i = ; i <= n; ++i) dis[i][i] = ;

        for (int i = ; i < m; ++i) {

            cin >> x >> y >> z;

            dis[x][y] = dis[y][x] = z;

        }

        floyd();

    //    cout << dis[1][n] << endl;

        for (int i = ; i <= n; ++i) {

            for (int j = ; j <= n; ++j) {

                if(j!=i) cout << "起点"<<i<<"到点" <<j<< "的最短距离是" << dis[i][j] << endl;

            }

            cout << endl;

        }

    }

    return ;

}