package main

import (
	"bytes"
	"io"
	"os"
	"sort"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') {
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return val
}

type Edge struct {
	u, v int
	w    int64
}

type DSU struct {
	parent []int
	size   []int
	low    []int64
}

func NewDSU(n int) *DSU {
	const inf int64 = 1 << 60
	parent := make([]int, n+1)
	size := make([]int, n+1)
	low := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
		size[i] = 1
		low[i] = inf
	}
	return &DSU{parent: parent, size: size, low: low}
}

func (d *DSU) Find(x int) int {
	r := x
	for d.parent[r] != r {
		r = d.parent[r]
	}
	for x != r {
		p := d.parent[x]
		d.parent[x] = r
		x = p
	}
	return r
}

func (d *DSU) Union(a, b int, w int64) {
	ra := d.Find(a)
	rb := d.Find(b)
	if ra == rb {
		if w < d.low[ra] {
			d.low[ra] = w
		}
		return
	}
	if d.size[ra] < d.size[rb] {
		ra, rb = rb, ra
	}
	d.parent[rb] = ra
	d.size[ra] += d.size[rb]
	if d.low[rb] < d.low[ra] {
		d.low[ra] = d.low[rb]
	}
	if w < d.low[ra] {
		d.low[ra] = w
	}
}

func main() {
	fs := NewFastScanner()
	t := fs.NextInt()
	var out bytes.Buffer

	for ; t > 0; t-- {
		n := fs.NextInt()
		m := fs.NextInt()
		edges := make([]Edge, m)
		for i := 0; i < m; i++ {
			u := fs.NextInt()
			v := fs.NextInt()
			w := fs.NextInt()
			edges[i] = Edge{u: u, v: v, w: int64(w)}
		}

		sort.Slice(edges, func(i, j int) bool {
			return edges[i].w < edges[j].w
		})

		dsu := NewDSU(n)
		const inf int64 = 1 << 60
		ans := inf

		for i := 0; i < m; {
			j := i
			w := edges[i].w
			for j < m && edges[j].w == w {
				dsu.Union(edges[j].u, edges[j].v, w)
				j++
			}

			r1 := dsu.Find(1)
			rn := dsu.Find(n)
			if r1 == rn {
				touched := false
				for k := i; k < j; k++ {
					if dsu.Find(edges[k].u) == r1 {
						touched = true
						break
					}
				}
				if touched {
					cand := w + dsu.low[r1]
					if cand < ans {
						ans = cand
					}
				}
			}

			i = j
		}

		out.WriteString(strconv.FormatInt(ans, 10))
		out.WriteByte('\n')
	}

	os.Stdout.Write(out.Bytes())
}