#include<bits/stdc++.h>
using namespace std;

const int maxn = 100 + 5;
const int INF = 1e9;  // 使用一个较大的数避免溢出
int mp[maxn][maxn];
int n, m;

void floyd(){
    for(int k = 1; k <= n; k ++) {
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++) {
                // 先判断是否可达，避免溢出
                if(mp[i][k] != INF && mp[k][j] != INF) {
                    mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
                }
            }
        }
    }
}

int main(){
    
    while(cin >> n >> m) {
        if(n == 0 && m == 0) break;
        
        // 初始化距离矩阵
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= n; j ++){
                if(i == j) mp[i][j] = 0;
                else mp[i][j] = INF;  // 使用自定义的INF
            }
        }
        
        // 读取边
        for(int i = 1; i <= m; i ++) {
            int u, v, w; cin >> u >> v >> ...