[模拟赛]提高2019-03-19

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
    char chr=getchar();    int f=1,ans=0;
    while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
    return ans*f;
}void write(int x){
    if(x>9) write(x/10),putchar(x%10+'0');
    else putchar(x+'0');
}int n,m,d[505][505],cnt[505][505],f[505][505],now[505];
#define F for(register int k(1);k<=n;++k)for(register int i(1);i<=n;++i)for(register int j(1);j<=n;++j)
signed main(){//freopen("path.in","r",stdin);freopen("path.out","w",stdout);    
    n=read(),m=read();
    memset(d,0x3f,sizeof d);for(register int i(0);i<=n;++i) d[i][i]=0;
    for(register int i(1),x,y;i<=m;++i)x=read(),y=read(),d[x][y]=d[y][x]=read();
    memcpy(f,d,sizeof d);
    F if(f[i][j]>f[i][k]+f[k][j])    f[i][j]=f[i][k]+f[k][j];
    for(register int i(1);i<=n;++i){
        for(register int j(1);j<=n;++j) now[j]=0;
        for(register int j(1);j<=n;++j) 
            for(register int k(1);k<=n;++k) if(k!=j&&f[i][j]+d[j][k]==f[i][k]) ++now[k];
        for(register int j(1);j<=n;++j)
            for(register int k(1);k<=n;++k)
                if(f[i][j]+f[j][k]==f[i][k]) cnt[i][k]+=now[j];
    }
    for(register int i(1);i<n;++i)
        for(register int j(i+1);j<=n;++j)
            if(f[i][j]==0x3f3f3f3f) putchar('0'),putchar(' ');else write(cnt[i][j]),putchar(' ');
    return 0;
}