Johnson
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9;
// 定义边的结构体，包含目标节点 v 和边的权重 w
struct edge { int v, w; };
// 邻接表存储图，e[i] 存储从节点 i 出发的所有边
vector<edge> e[N];
// vis 数组用于标记节点是否在队列中，cnt 数组用于记录每个节点入队的次数
int vis[N], cnt[N];
// h 数组用于存储从虚拟源点到各节点的最短路，d 数组用于存储从某个源点到各节点的最短路
long long h[N], d[N];
int n, m;
// 使用 SPFA 算法计算从虚拟源点 0 到其他所有节点的最短路
void spfa() {
// 定义一个队列用于存储待处理的节点
queue<int> q;
// 初始化 h 数组为一个很大的值，memset(63) 相当于将每个元素初始化为一个较大的数
memset(h, 63, sizeof h);
memset(vis, false, sizeof vis);
// 虚拟源点到自身的距离为 0
h[0] = 0;
// 标记虚拟源点在队列中
vis[0] = 1;
// 将虚拟源点加入队列
q.push(0);
while (q.size()) {
int u = q.front();
q.pop();
// 标记该节点不在队列中
vis[u] = 0;
// 遍历从节点 u 出发的所有边
for (auto ed : e[u]) {
// 获取目标节点 v 和边的权重 w
int v = ed.v, w = ed.w;
// 如果通过节点 u 到达节点 v 的距离更短，则更新 h[v]
if (h[v] > h[u] + w) {
h[v] = h[u] + w;
// 更新节点 v 的入队次数
cnt[v] = cnt[u] + 1;
// 如果某个节点入队次数超过 n 次，说明存在负环
if (cnt[v] > n) {
printf("-1\n");
// 存在负环，程序退出
exit(0);
}
// 如果节点 v 不在队列中，则将其加入队列
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
}
// 使用 Dijkstra 算法计算从源点 s 到其他所有节点的最短路
void dijkstra(int s) {
// 定义一个优先队列，用于存储待处理的节点，按照距离从小到大排序
priority_queue<pair<long long, int>> q;
// 初始化 d 数组为无穷大
for (int i = 1; i <= n; i++) {
d[i] = INF;
}
// 初始化 vis 数组为 false，表示所有节点都未被处理
memset(vis, false, sizeof vis);
// 源点到自身的距离为 0
d[s] = 0;
// 将源点加入优先队列
q.push({ 0,s });
// 当优先队列不为空时进行处理
while (q.size()) {
// 取出队首节点
int u = q.top().second;
q.pop();
// 如果该节点已经被处理过，则跳过
if (vis[u]) {
continue;
}
// 标记该节点已被处理
vis[u] = 1;
// 遍历从节点 u 出发的所有边
for (auto ed : e[u]) {
// 获取目标节点 v 和边的权重 w
int v = ed.v;
int w = ed.w;
// 如果通过节点 u 到达节点 v 的距离更短，则更新 d[v]
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
// 如果节点 v 未被处理，则将其加入优先队列
if (!vis[v]) {
q.push({ -d[v],v });
}
}
}
}
}
int main() {
cin >> n >> m;
// 输入每条边的信息，并将其加入邻接表
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
e[a].push_back({ b,c });
}
// 从虚拟源点 0 向其他所有节点添加一条边权为 0 的边
for (int i = 1; i <= n; i++) {
e[0].push_back({ i,0 });//加虚拟边
}
// 调用 SPFA 算法计算从虚拟源点到其他所有节点的最短路
spfa();
// 对图的边权进行重新计算，确保所有边权非负
for (int u = 1; u <= n; u++) {
for (auto& ed : e[u]) {
ed.w += h[u] - h[ed.v];//构造新边
}
}
// 以每个节点为源点，调用 Dijkstra 算法计算最短路
for (int i = 1; i <= n; i++) {
dijkstra(i);
long long ans = 0;
// 计算从源点 i 到其他所有节点的最短路的加权和
for (int j = 1; j <= n; j++) {
// 如果节点 j 不可达，则使用无穷大计算
if (d[j] == INF) {
ans += (long long)j * INF;
}
// 否则，使用实际距离计算
else {
ans += (long long)j * (d[j] + h[j] - h[i]);
}
}
// 输出结果
printf("%lld\n", ans);
}
return 0;
}