ダイクストラ． サイクルを含んでいるので注意． サイクルだけ別に管理してしまうと楽．
始点を \(s \in N\) とする良い path を考えると， [\(s \rightarrow s\) のループを使う path] または， [\(s \rightarrow i \rightarrow s\) かつ \(i \neq s\) となる path] のいずれか． ここで，\(s \rightarrow i, \ i \rightarrow s\) は 共にループを持たないとしてよい．
実装:
ループを持たないグラフでダイクストラをする． それとは別に，ループを使ったケースを調べる．
\(i \rightarrow s\) は，edge の向きを逆にしたグラフで ダイクストラしても良いし，辺だと思ってもよい． つまり，\(s\) 以外で最後に訪れる頂点 \(i\) を全探索するということ． これは，ハミルトン閉路の実装と似ている．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct EDGE{
ll to, cost;
EDGE(){}
EDGE(ll to, ll cost): to(to), cost(cost){}
};
int main() {
ll n, m;
cin >> n >> m;
vvll co(n, vll(n,INFL));
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
if(a != b){
g[a].push_back(EDGE(b, c));
chmin(co[a][b], c);
}
else{
cyc[a].push_back(EDGE(a, c));
}
}
auto diji = [&](ll src) -> void {
min_priority_queue<pll> q;
dis[src] = 0;
q.push({0,src});
while(q.size()){
auto [cd, cv] = q.top(); q.pop();
if(dis[cv] != cd) continue;
for(auto [nv, nco]: g[cv]){
ll nd = cd + nco;
if(chmin(dis[nv], nd)){
q.push({nd, nv});
}
}
}
ll ans = INFL;
for(auto [_, cost]: cyc[src]){
chmin(ans, cost);
}
rep(i,n) if(i != src){
chmin(ans, dis[i] + co[i][src]);
}
if(ans >= INFL) ans = -1;
cout << ans << endl;
};
rep(i,n){
diji(i);
}
return 0;
}
