1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <queue>  6 using namespace std;  7   8 #define MAXN 105  9 #define INF  1000001 10  11 int n, m; 12 int map[MAXN][MAXN], al[MAXN], bk[MAXN], path[MAXN]; 13 bool visit[MAXN]; 14 int low, high; 15 int ans, dif; 16  17 int dijkstra() { 18     int i, j, v, min; 19  20     if (al[1]<low || al[1]>high) 21         return INF; 22  23     memset(visit, false, sizeof(visit)); 24     visit[1] = true; 25     for (i=1; i<=n; ++i) { 26         if (al[i]>=low && al[i]<=high) 27             path[i] = map[1][i]; 28         else 29             path[i] = INF; 30     } 31  32     for (i=1; i<n; ++i) { 33         min = INF; 34         for (j=1; j<=n; ++j) { 35             if (!visit[j] && path[j]<min) { 36                 v = j; 37                 min = path[j]; 38             } 39         } 40         if (min == INF) 41             break; 42         visit[v] = true; 43         for (j=1; j<=n; ++j) { 44             if (!visit[j] && map[v][j]+min<path[j] && al[j]>=low && al[j]<=high) 45                 path[j] = map[v][j] + min; 46         } 47     } 48     return path[n]; 49 } 50  51 int main() { 52     int t, min, l, r, max, mid; 53     int i, j, k, tmp; 54  55     scanf("%d", &t); 56     while (t--) { 57         scanf("%d %d", &n, &m); 58         min = dif = 1000000001; 59         ans = INF; 60         max = 0; 61         for (i=1; i<=n; ++i) { 62             scanf("%d", &al[i]); 63             if (al[i] < min) min = al[i]; 64             if (al[i] > max) max = al[i]; 65             bk[i] = al[i]; 66         } 67         for (i=1; i<=n; ++i) { 68             map[i][i] = 0; 69             for (j=i+1; j<=n; ++j) 70                 map[i][j] = map[j][i] = INF; 71         } 72         while (m--) { 73             scanf("%d %d %d", &i, &j, &k); 74             if (map[i][j] > k) 75                 map[i][j] = map[j][i] = k; 76         } 77         sort(bk+1, bk+1+n); 78         l = 0; r = max-min+1; 79         while (l < r) { 80             mid = (l + r)>>1; 81             bool flag = false; 82             for (i=1; i<=n; ++i) { 83                 low = bk[i]; 84                 high = bk[i] + mid; 85                 tmp = dijkstra(); 86                 if (tmp != INF) { 87                     flag = true; 88                     break; 89                 } 90             } 91             if ( flag ) { 92                 if (mid < dif) { 93                     dif = mid; 94                     ans = tmp; 95                 } else if (mid==dif && ans > tmp) { 96                     ans = tmp; 97                 } 98                 r = mid; 99             } else {100                 l = mid + 1;101             }102         }103         printf("%d %d\n", dif, ans);104     }105 106     return 0;107 }