ll@n,@m,@p[n];
int@(u--,v--,t)[m];
wgraph<int>g;
g.setDirectEdge(n,m,u,v,t);
ll z=ll_inf,c=0;
rep(i,n){
	ll d[n];
	g.BellmanFord(i,d,-ll_inf,-ll_inf);
	rep(j,n){
		if(i!=j&&d[j]>-ll_inf){
			ll e=d[j]+p[i]+p[j];
			if(z>e){
				z=e;
				c=0;
			}
			if(z==e){
				++c;
			}
		}
	}
}
wt(z,c);