
/*#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<deque>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
//#define __int64 long long
#define P pair<int,int>
string s;

int n,m;
vector<P>G[1005];
bool ok[105][105];
bool is[105][105];
int dist[105];
int d[105][105];
const int INF=100000000;

void daiku(int from,int to){
	priority_queue<P,vector<P>,greater<P> >bfs;
	bfs.push(mp(0,from));
	rep(i,n)dist[i]=INF;

	while(!bfs.empty()){
		P t=bfs.top();
		bfs.pop();
		int next=t.second,cost=t.first;
		if(dist[next]!=INF)continue;
		dist[next]=cost;
		rep(i,G[next].size()){
			bfs.push(mp(cost+G[next][i].second,G[next][i].first));
		}
	}
	//cout<<from<<" "<<to<<" "<<dist[to]<<endl;
	int now=to;
	rep(i,n)d[from][i]=dist[i];
}

int main(){
	cin>>n>>m;	
	int a,b,c;
	rep(i,m){
		cin>>a>>b>>c;
		a--;b--;
		G[a].pb(mp(b,c));
		G[b].pb(mp(a,c));
		is[a][b]=is[b][a]=1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j)daiku(i,j);
		}
	}

	int ans=0;
	rep(i,n){
		rep(j,n)cout<<d[i][j]<<" ";
		cout<<endl;
	}
	cout<<ans<<endl;
}
*/