/VOI 13 Bài 5 - Hành trình du lịch

              #include <iostream>
        #include <vector>
        #include <queue>
        #include <algorithm>
        using namespace std;
        
        struct Edge {
          int u, v, c;
        };
        
        typedef vector<Edge>::iterator iter;
        
        struct pack {
          long long s;
          iter it;
        };
        
        bool operator < (const pack &a, const pack &b) {
          return a.s > b.s;
        }
        
        void showVector(vector<Edge> E);
        
        int dijkstra(int x, vector<Edge> &E, vector<iter> &s) {
          if (s[x] == E.end()) return -1;
        
          vector<long long> f(s.size(), 0);
          priority_queue<pack> iDex;
        
          iDex.push({ s[x]->c, s[x] });
        
          while (!iDex.empty()) {
            pack t = iDex.top();
        
            if (t.it->v == x) return t.s;
        
            f[t.it->v] = t.s;
        
            if (s[t.it->v] != E.end()) {
              iDex.push({t.s + s[t.it->v]->c, s[t.it->v]});
            }
        
            while (f[iDex.top().it->v]) {
              iter it = iDex.top().it;
              iDex.pop();
        
              int u = it->u;
        
              while (it != E.end() && it->u == u) {
                if (!f[it->v]) {
                  iDex.push({ f[u] + it->c, it });
                  break;
                }
                it++;
              }
            }
          }
          return -1;
        }
        
        int main() {
          ios::sync_with_stdio(false); cin.tie(0);
          int T;
          cin >> T;
        
          while (T--) {
            int n, m;
            cin >> n >> m;
        
            vector<Edge> E(m);
        
            for (auto& it : E) {
              cin >> it.u >> it.v >> it.c;
              it.u--;
              it.v--;
            }
        
            sort(E.begin(), E.end(), [](const Edge &a, const Edge &b) {
              return a.c < b.c;
              });
        
            stable_sort(E.begin(), E.end(), [](const Edge &a, const Edge &b) {
              return a.u < b.u;
              });
        
            vector<iter> s(n, E.end()); // mark
        
            for (auto it = E.begin(); it != E.end(); it++) {
              if (s[it->u] == E.end()) s[it->u] = it;
            }
        
            for (int i = 0; i < n; i++) {
              cout << dijkstra(i, E, s) << endl;
            }
        
          }
          return 0;
        }
        
        void showVector(vector<Edge> E) {
          for (auto it : E) {
            cout << it.u << " " << it.v << " " << it.c << endl;
          }
        }