lib C;fun strtoll(s: UInt8*, p: UInt8**, b: Int32): Int64;end class String;def to_i64;C.strtoll(self,nil,10);end;end I=10i64**18 n,m=read_line.split.map(&.to_i) d=(1..n).map{[I]*n} n.times{|i|d[i][i]=0} m.times{s,t,c=read_line.split.map(&.to_i64.pred);d[s][t]={d[s][t],c+1}.min} n.times{|i|n.times{|j|n.times{|k|d[j][k]={d[j][k],d[j][i]+d[i][k]}.min}}} n.times{|i|p (0...n).sum{|j|d[i][j]