#include using namespace std; #pragma region atcoder //#include //using namespace atcoder; //using mint = modint998244353; //using mint = modint1000000007; #pragma endregion #pragma region debug for var, v, vv #define debug(var) do{std::cerr << #var << " : ";view(var);}while(0) template void view(T e){std::cerr << e << std::endl;} template void view(const std::vector& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;} template void view(const std::vector >& vv){cerr << endl;int cnt = 0;for(const auto& v : vv){cerr << cnt << "th : "; view(v); cnt++;} cerr << endl;} #pragma endregion using ll = long long; const ll mod = 1000000007; const int inf = 1001001001; const ll INF = 1001001001001001001ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; templatebool chmax(T &a, const K b) { if (abool chmin(T &a, const K b) { if (b0&&a%b); } // 20 / 3 == 7 ll rddiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // -20 / 3 == -7 ll power(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a;} a = a * a; p >>= 1;} return ret;} ll modpow(ll a, ll p, ll m){ll ret = 1; while(p){if(p & 1){ret = ret * a % m;} a = a * a % m; p >>= 1;} return ret;} /*---------------------------------------------------------------------------------------------------------------------------------*/ ll dist[101]; bool used[101]; void dijkstra(vector> &G, int s){ int n = G.size(); dist[s] = 0; while(true){ int v = -1; for(int i = 0; i < n; i++){ if(!used[i] && (v == -1 || dist[i] < dist[v])) v = i; } if(v == -1) break; used[v] = true; for(int i = 0; i < n; i++){ if(chmin(dist[i], dist[v] + G[v][i])) used[i] = false; } } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); //cout << fixed << setprecision(20); int n, m; cin >> n >> m; vector> G(n, vector(n)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) G[i][j] = INF; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; a--, b--; ll d; cin >> d; chmin(G[a][b], d); } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) dist[j] = INF; dijkstra(G, i); ll ans = 0; memset(used, 0, sizeof(used)); for(int j = 0; j < n; j++){ ans += (dist[j] >= INF ? 0 : dist[j]); } ans -= dist[i]; cout << ans << endl; } } /* * review you code when you get WA (typo? index?) * int overflow, array bounds * special cases (n=1?) */