照理说O(mn^2)的算法能过，可是我总是TLE。
#include <cstdio>
#include <cstring>
#define ele int
using namespace std;
#define INF 200000000
#define maxn 110
ele n,m,g[maxn][maxn];
#define min(a,b) ((a)<(b))?(a):(b)
inline void get(ele &a){
char in;
while ((in=getchar())<'0' || in>'9');
a=in-'0';
while ((in=getchar())>='0' && in<='9')
a*=10,a+=in-'0';
}
inline void put(ele a){
if (a>=10) put(a/10);
putchar(a%10+'0');
}
inline void init(){
get(n); get(m);
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
g[i][j]=INF*(i!=j);
}
inline void solve(){
ele c,a,b,k;
while (m--){
get(c); get(a); get(b);
if (c) get(k);
--a,--b;
if (!c)
if (g[a][b]>=INF)
puts("-1");
else
put(g[a][b]),putchar('\n');
else{
g[a][b]=min(g[a][b],k);
g[b][a]=g[a][b];
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j){
g[i][j]=min(g[i][j],g[i][a]+g[a][b]+g[b][j]);
g[i][j]=min(g[i][j],g[i][b]+g[b][a]+g[a][j]);
}
}
}
}
int main(){
init();
solve();
return 0;
}