// T must define < and +
template<typename T,size_t V,bool Directed=true,T INF=T(0x3f3f3f3f)>
struct Floyd {
    T g[V][V];
    int n;
    void init(int n_)
    {
        n=n_;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) g[i][j]=INF;
    }
    void addedge(int u,int v,T w) // check multi-edges
    {
        g[u][v]=w; 
        if(!Directed) g[v][u]=w;
    }
    void cmin(T &x,const T &y) { if(y<x) x=y; }
    void floyd(Upd =upd)
    {
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    cmin(g[i][j],g[i][k]+g[k][j]);
    }
};