记录 TLE应该是常数问题，WA是怎么回事QAQ

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 3000
#define inf (1ll * 1000000000)
#define int long long

struct side {
    int to, length;
};
std :: vector <side> S[maxn + 10];
int n, m, u, v, w, have;
int bl[maxn + 10], dl[maxn + 10][maxn + 10];
int vis[maxn + 10], dis[maxn + 10], tr[maxn << 2];

inline void Bellman_Ford() {
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j <= n; j++)
            for (int k = 0, maxk = S[j].size(); k < maxk; k++)
                bl[S[j][k].to] = std :: min(bl[S[j][k].to], bl[j] + S[j][k].length);
    for (int j = 0; j <= n; j++)
        for (int k = 0, maxk = S[j].size(); k < maxk; k++)
            if (bl[j] + S[j][k].length <  bl[S[j][k].to]) {
                have = 1;
                return;
            }
    return;
}
inline void build(int i, int l, int r, int p) {
    if (l == r) {
        if (l == p) tr[i] = inf + 1;
        else tr[i] = dl[p][l];
        return;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid, p), build((i << 1) + 1, mid + 1, r, p);
    tr[i] = std :: min(tr[i << 1], tr[(i << 1) + 1]);
    return;
}
inline int findmin(int i, int l, int r) {
    if (l == r) return l;
    int mid = l + r >> 1, ls = i << 1, rs = (i << 1) + 1;
    if (tr[ls] < tr[rs]) return findmin(ls, l, mid);
    else return findmin(rs, mid + 1, r);
}
inline void pushin(int i, int l, int r, int p, int num) {
    if (l == r) {
        tr[i] = num; return;
    }
    int mid = l + r >> 1, ls = i << 1, rs = (i << 1) + 1;
    if (p <= mid) pushin(ls, l, mid, p, num);
    else pushin(rs, mid + 1, r, p, num);
    tr[i] = std :: min(tr[ls], tr[rs]);
    return;
}
inline int dijkstra(int id) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        vis[i] = 0, dis[i] = inf;
    vis[id] = 1;
    for (int j = 0, maxj = S[id].size(); j < maxj; j++)
        dis[S[id][j].to] = dl[id][S[id][j].to];
    build(1, 1, n, id);
    for (int num = 1; num < n; num++) {
        int now = findmin(1, 1, n);
        sum += now * std :: min(dis[now] - bl[id] + bl[now], inf);
//        printf("%lld %lld %lld\n", id, now, dis[now] - bl[id] + bl[now]);
        pushin(1, 1, n, now, inf + 1);
        vis[now] = 1;
        for (int i = 0, maxi = S[now].size(); i < maxi; i++)
            if (!vis[S[now][i].to] && dis[now] + dl[now][S[now][i].to] < dis[S[now][i].to]) {
            	dis[S[now][i].to] = dis[now] + dl[now][S[now][i].to];
            	pushin(1, 1, n, S[now][i].to, dis[S[now][i].to]);
			}
	}
    return sum;
}

signed main(void) {
	//freopen("in.in", "r", stdin); 
    scanf("%lld %lld", &n, &m);
    while (m--)
        scanf("%lld %lld %lld", &u, &v, &w), S[u].push_back({v, w});
    for (int i = 1; i <= n; i++)
        S[0].push_back({i, 0}), bl[i] = inf;
    Bellman_Ford();
    if (have) {
        puts("-1");
        return 0;
    }
//    for (int i = 1; i <= n; i++)
//        printf("%lld\n", bl[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j) dl[i][j] = inf;
    for (int i = 1; i <= n; i++)
        for (int j = 0, maxj = S[i].size(); j < maxj; j++)
            dl[i][S[i][j].to] = std :: min(dl[i][S[i][j].to], S[i][j].length + bl[i] - bl[S[i][j].to]);
//    for (int i = 1; i <= n; i++, putchar('\n'))
//        for (int j = 1; j <= n; j++) printf("%lld ", dl[i][j] - bl[i] + bl[j]);
    for (int i = 1; i <= n; i++)
        printf("%lld\n", dijkstra(i));
    
    return 0;
}