1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 int head[1000005],n, m, cnt, ccnt; 7 long long dist[1000005],ans; 8 struct pot { 9 int id; 10 int val; 11 bool operator<(const struct pot&aa)const { 12 return val > aa.val; 13 } 14 }; 15 struct edge { 16 int fr; 17 int to; 18 long long v; 19 int next; 20 }e[1000005]; 21 void INIT() { 22 memset(head, -1, sizeof(head)); 23 memset(dist, 0x3f3f3f3f, sizeof(dist)); 24 dist[1] = 0; 25 cnt=0; 26 ans = 0; 27 } 28 void adde(int xx, int yy,long long zz) { 29 e[cnt].fr = xx; 30 e[cnt].to = yy; 31 e[cnt].v = zz; 32 e[cnt].next = head[xx]; 33 head[xx] = cnt++; 34 } 35 void dij() { 36 priority_queue<struct pot>pq; 37 struct pot sta; 38 sta.id = 1; 39 sta.val = 0; 40 pq.push(sta); 41 while (!pq.empty()) { 42 struct pot aa = pq.top(); pq.pop(); 43 if (dist[aa.id] < aa.val)continue; 44 for (int i = head[aa.id]; i != -1; i = e[i].next) { 45 if (dist[e[i].to] > dist[aa.id] + e[i].v) { 46 dist[e[i].to] = dist[aa.id] + e[i].v; 47 struct pot cc; 48 cc.id = e[i].to; 49 cc.val = dist[e[i].to]; 50 pq.push(cc); 51 } 52 } 53 } 54 } 55 int main() { 56 int t; 57 scanf("%d",&t); 58 while (t--) { 59 INIT(); 60 scanf("%d%d", &n, &m); 61 while (m--) { 62 int x, y; 63 long long z; 64 scanf("%d%d%lld", &x, &y, &z); 65 adde(x, y, z); 66 } 67 dij(); 68 } 69 return 0; 70 }