#include <stdio.h>
#include <map>
#include <vector>
#include <queue>
#include <stdint.h>
using namespace std;

int C, N, M;
//A,B 도시 사이 코스트 C, A<<16+B --> C
map<int, int64_t> Link;
#define KEY(x,y) ((x<<16)+y)
int64_t cost_so_far[10000];
typedef vector<int> V;

struct Node {
    Node(int n) :
            n(n) {
    }
    int n;
    bool operator<(const Node &t) const {
        return cost_so_far[n] > cost_so_far[t.n];
    }
};

int64_t f(V neighbors[]) {
    priority_queue<Node> q;
    cost_so_far[0] = 0, q.push(Node(0));
    for (int i = 1; i < N; ++i)
        cost_so_far[i] = 10e17, q.push(i);  // 두도시 사이의 default cost==10e17

    while (q.size()) {
        Node u = q.top();
        q.pop();
        if (u.n == N - 1)
            break;
        for (V::iterator it = neighbors[u.n].begin();
                it != neighbors[u.n].end(); ++it) {
            int64_t t = cost_so_far[u.n] + Link[KEY(u.n, *it)];
            if (t < cost_so_far[*it])
                cost_so_far[*it] = t;
        }
    }
    return cost_so_far[N - 1];
}

int main() {
    scanf("%d", &C);
    while (--C >= 0) {
        // 이웃 도시 정보 저장 0도시 의 이웃 도시가 1,2,3이라면, neighbors[0] --> Vector[1,2,3]
        V neighbors[10000];
        scanf("%d%d", &N, &M);
        for (int i = 0; i < M; ++i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if (Link.find(KEY(a, b)) == Link.end() //아직 읽지 않은 경로거나
                    || (Link.find(KEY(a, b)) != Link.end() && Link[KEY(a, b)] > c)) { // 읽었지만, 짧다면
                Link[KEY(a, b)] = Link[KEY(b, a)] = c;
                neighbors[a].push_back(b), neighbors[b].push_back(a);
            }
        }
        printf("%I64d\n", f(neighbors));
    }
}