import java.io.*;
import java.util.*;
 
public class Main {
    static class Edge {
        int to;
        long w;
        Edge(int to, long w) { this.to = to; this.w = w; }
    }
 
    static long[] minimaxDijkstra(int src, List<Edge>[] adj, int n) {
        long[] dist = new long[n+1];
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        dist[src] = 0;
        pq.offer(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0];
            int u = (int)cur[1];
            if (d > dist[u]) continue;
            for (Edge e : adj[u]) {
                long nd = Math.max(d, e.w);
                if (nd < dist[e.to]) {
                    dist[e.to] = nd;
                    pq.offer(new long[]{nd, e.to});
                }
            }
        }
        return dist;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
            List<Edge>[] adj = new List[n+1];
            for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
            int[] U = new int[m], V = new int[m];
            long[] W = new long[m];
            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                U[i] = Integer.parseInt(st.nextToken());
                V[i] = Integer.parseInt(st.nextToken());
                W[i] = Long.parseLong(st.nextToken());
                adj[U[i]].add(new Edge(V[i], W[i]));
                adj[V[i]].add(new Edge(U[i], W[i]));
            }
            long[] dist1 = minimaxDijkstra(1, adj, n);
            long[] distN = minimaxDijkstra(n, adj, n);
            long ans = Long.MAX_VALUE;
            for (int i = 0; i < m; i++) {
                int u = U[i], v = V[i];
                long w = W[i];
                long c1 = w + Math.max(w, Math.max(dist1[u], distN[v]));
                long c2 = w + Math.max(w, Math.max(dist1[v], distN[u]));
                ans = Math.min(ans, Math.min(c1, c2));
            }
            out.println(ans);
        }
        out.flush();
    }
}
 

aW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewogICAgc3RhdGljIGNsYXNzIEVkZ2UgewogICAgICAgIGludCB0bzsKICAgICAgICBsb25nIHc7CiAgICAgICAgRWRnZShpbnQgdG8sIGxvbmcgdykgeyB0aGlzLnRvID0gdG87IHRoaXMudyA9IHc7IH0KICAgIH0KCiAgICBzdGF0aWMgbG9uZ1tdIG1pbmltYXhEaWprc3RyYShpbnQgc3JjLCBMaXN0PEVkZ2U+W10gYWRqLCBpbnQgbikgewogICAgICAgIGxvbmdbXSBkaXN0ID0gbmV3IGxvbmdbbisxXTsKICAgICAgICBBcnJheXMuZmlsbChkaXN0LCBMb25nLk1BWF9WQUxVRSk7CiAgICAgICAgUHJpb3JpdHlRdWV1ZTxsb25nW10+IHBxID0gbmV3IFByaW9yaXR5UXVldWU8PihDb21wYXJhdG9yLmNvbXBhcmluZ0xvbmcoYSAtPiBhWzBdKSk7CiAgICAgICAgZGlzdFtzcmNdID0gMDsKICAgICAgICBwcS5vZmZlcihuZXcgbG9uZ1tdezAsIHNyY30pOwogICAgICAgIHdoaWxlICghcHEuaXNFbXB0eSgpKSB7CiAgICAgICAgICAgIGxvbmdbXSBjdXIgPSBwcS5wb2xsKCk7CiAgICAgICAgICAgIGxvbmcgZCA9IGN1clswXTsKICAgICAgICAgICAgaW50IHUgPSAoaW50KWN1clsxXTsKICAgICAgICAgICAgaWYgKGQgPiBkaXN0W3VdKSBjb250aW51ZTsKICAgICAgICAgICAgZm9yIChFZGdlIGUgOiBhZGpbdV0pIHsKICAgICAgICAgICAgICAgIGxvbmcgbmQgPSBNYXRoLm1heChkLCBlLncpOwogICAgICAgICAgICAgICAgaWYgKG5kIDwgZGlzdFtlLnRvXSkgewogICAgICAgICAgICAgICAgICAgIGRpc3RbZS50b10gPSBuZDsKICAgICAgICAgICAgICAgICAgICBwcS5vZmZlcihuZXcgbG9uZ1tde25kLCBlLnRvfSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGRpc3Q7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgdGhyb3dzIElPRXhjZXB0aW9uIHsKICAgICAgICBCdWZmZXJlZFJlYWRlciBiciA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CiAgICAgICAgUHJpbnRXcml0ZXIgb3V0ID0gbmV3IFByaW50V3JpdGVyKFN5c3RlbS5vdXQpOwogICAgICAgIGludCB0ID0gSW50ZWdlci5wYXJzZUludChici5yZWFkTGluZSgpLnRyaW0oKSk7CiAgICAgICAgd2hpbGUgKHQtLSA+IDApIHsKICAgICAgICAgICAgU3RyaW5nVG9rZW5pemVyIHN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihici5yZWFkTGluZSgpKTsKICAgICAgICAgICAgaW50IG4gPSBJbnRlZ2VyLnBhcnNlSW50KHN0Lm5leHRUb2tlbigpKSwgbSA9IEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwogICAgICAgICAgICBMaXN0PEVkZ2U+W10gYWRqID0gbmV3IExpc3RbbisxXTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBhZGpbaV0gPSBuZXcgQXJyYXlMaXN0PD4oKTsKICAgICAgICAgICAgaW50W10gVSA9IG5ldyBpbnRbbV0sIFYgPSBuZXcgaW50W21dOwogICAgICAgICAgICBsb25nW10gVyA9IG5ldyBsb25nW21dOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewogICAgICAgICAgICAgICAgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkpOwogICAgICAgICAgICAgICAgVVtpXSA9IEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwogICAgICAgICAgICAgICAgVltpXSA9IEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwogICAgICAgICAgICAgICAgV1tpXSA9IExvbmcucGFyc2VMb25nKHN0Lm5leHRUb2tlbigpKTsKICAgICAgICAgICAgICAgIGFkaltVW2ldXS5hZGQobmV3IEVkZ2UoVltpXSwgV1tpXSkpOwogICAgICAgICAgICAgICAgYWRqW1ZbaV1dLmFkZChuZXcgRWRnZShVW2ldLCBXW2ldKSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbG9uZ1tdIGRpc3QxID0gbWluaW1heERpamtzdHJhKDEsIGFkaiwgbik7CiAgICAgICAgICAgIGxvbmdbXSBkaXN0TiA9IG1pbmltYXhEaWprc3RyYShuLCBhZGosIG4pOwogICAgICAgICAgICBsb25nIGFucyA9IExvbmcuTUFYX1ZBTFVFOwogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG07IGkrKykgewogICAgICAgICAgICAgICAgaW50IHUgPSBVW2ldLCB2ID0gVltpXTsKICAgICAgICAgICAgICAgIGxvbmcgdyA9IFdbaV07CiAgICAgICAgICAgICAgICBsb25nIGMxID0gdyArIE1hdGgubWF4KHcsIE1hdGgubWF4KGRpc3QxW3VdLCBkaXN0Tlt2XSkpOwogICAgICAgICAgICAgICAgbG9uZyBjMiA9IHcgKyBNYXRoLm1heCh3LCBNYXRoLm1heChkaXN0MVt2XSwgZGlzdE5bdV0pKTsKICAgICAgICAgICAgICAgIGFucyA9IE1hdGgubWluKGFucywgTWF0aC5taW4oYzEsIGMyKSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgb3V0LnByaW50bG4oYW5zKTsKICAgICAgICB9CiAgICAgICAgb3V0LmZsdXNoKCk7CiAgICB9Cn0K

NAozIDIKMSAyIDEKMiAzIDEKMyAyCjEgMyAxMwoxIDIgNQo4IDkKMSAyIDYKMiAzIDUKMyA4IDYKMSA0IDcKNCA1IDQKNSA4IDcKMSA2IDUKNiA3IDUKNyA4IDUKMyAzCjEgMyA5CjEgMiA4CjIgMyAzCg==

4
3 2
1 2 1
2 3 1
3 2
1 3 13
1 2 5
8 9
1 2 6
2 3 5
3 8 6
1 4 7
4 5 4
5 8 7
1 6 5
6 7 5
7 8 5
3 3
1 3 9
1 2 8
2 3 3