#include<stdio.h>
#include<stdlib.h>

int C, N, M;

int num_visit = 0;

typedef struct Node{
    int no; // node의 번호
//정렬된 edge 배열에서 해당 노드가 포함되는 edge가 시작되는 index
    int start; 
// 정렬된 edge 배열에서 해당 노드가 포함되는 edge가 끝나는 index
    int end;   
    double distance; // 해당 노드까지 오는 최소 cost
}NODE;

typedef struct Edge{
    int n1;  // 시작 노드
    int n2;  // 끝 노드 
    double w;  // edge의 distance
    // 다익스트라 알고리즘에서 edge 사용 유무. 한번 사용했으면 true
    bool visit;  
}EDGE;


NODE heap_nodes[10010];  // 노드들을 힙트리? 우선순위큐? 형태로 저장할때 쓰이는 배열
int heap_end;            

// edge들을 저장해놓은 배열.  
//n1 크기가 작은 순서에서 큰 순서대로 정렬되어 있음
EDGE edges[50000];       

// 이 배열의 index에  해당하는 노드가, 
//heap_nodes에서 무슨 index에 저장되어있는지 가지고 있음
// e.g.) heap_idx[5] = 10 ->  
//5번 노드는 heap_nodes 배열에서 10번에 저장되어있음
int heap_idx[10010]; 


// 각 노드의 각 노드까지 오는 최소 cost
// e.g.) distance[5] = 10  ->  5번 노드까지 오는 최소 cost는 10
double distance[10010];   

// 힙트리에서 노드 스왑 + 
// 힙트리에서의 인덱스 저장해놓은 배열에서도 스왑
void swap(int idx1, int idx2)
{
    NODE tmp2;
    int tmp;

    //node들의 heap 배열에서의 index 교환
    tmp = heap_idx[heap_nodes[idx1].no];
    heap_idx[heap_nodes[idx1].no] = heap_idx[heap_nodes[idx2].no];
    heap_idx[heap_nodes[idx2].no] = tmp;

    //heap 배열에서 노드 교환
    tmp2 = heap_nodes[idx1];
    heap_nodes[idx1] = heap_nodes[idx2];
    heap_nodes[idx2] = tmp2;
}


// 가장 distance가 작은 노드가 root에 있는 트리 만들기
// heap_nodes 배열로 구현. 배열 1번이 root.
void push(NODE n)
{

    heap_end++;

    heap_nodes[heap_end] = n;
    heap_idx[n.no] = heap_end;

    if (heap_end > 1)
    {
        int idx = heap_end;
        int parent = heap_end / 2;
        while (heap_nodes[parent].distance > heap_nodes[idx].distance)
        {
            swap(idx, parent);
            idx = parent;
            parent = idx / 2;
            if (parent == 0) break;
        }
    }

}


// 가장 distance가 작은 노드 return -> heap_nodes[1] return.
NODE pop()
{

    NODE ret = heap_nodes[1];

    heap_idx[heap_nodes[1].no] = -1;
    heap_nodes[1] = heap_nodes[heap_end];
    heap_idx[ heap_nodes[heap_end].no ] = 1;

    heap_end--;

    int parent = 1;
    int ch1 = 2;
    while (1)
    {
        if (heap_nodes[ch1].distance > heap_nodes[ch1 + 1].distance)
            ch1++;

        if (heap_nodes[ch1].distance < heap_nodes[parent].distance)
        {
            swap(parent, ch1);

            parent = ch1;
            ch1 = parent * 2;

        }
        else break;
        if (ch1 > heap_end) break;
    }

    return ret;
}


//다익스트라 알고리즘 수행시 노드의 distance가 수정 될 경우, 
//수정한 뒤에
//힙트리에서 노드의 위치가 바뀌어야 한다면 바꾸는 함수
void edit(int idx, double w)
{
    //노드 distance 수정
    heap_nodes[idx].distance = w;

    //힙트리에서 위치 다시 찾기
    //distance가 현재 값에서 작아지기만 하므로 
    //parent보다 작은지만 계속 검사
    int parent = idx / 2;
    while (parent>0)
    {
        if (heap_nodes[parent].distance > heap_nodes[idx].distance)
        {
            swap(parent, idx);
        }
        else break;
        idx = parent;
        parent = idx / 2;
    }

}

// merge sort. edge 정렬에 사용
EDGE tmp[40000];
void merge(int left, int mid, int right)
{
    int l = left;
    int r = mid + 1;
    int idx = 0;

    while (l <= mid && r <= right)
    {
        if (edges[l].n1 < edges[r].n1) tmp[idx++] = edges[l++];
        else if (edges[l].n1 > edges[r].n1) tmp[idx++] = edges[r++];
        else
        {
            if (edges[l].n2 <= edges[r].n2) tmp[idx++] = edges[l++];
            else tmp[idx++] = edges[r++];
        }
    }

    while (l <= mid) tmp[idx++] = edges[l++];
    while (r <= right) tmp[idx++] = edges[r++];

    for (int i = left; i <= right; i++)
        edges[i] = tmp[i-left];

}

void merge_sort(int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;

        merge_sort(left, mid);
        merge_sort(mid + 1, right);
        merge(left, mid, right);
    }
}




int main()
{

    int a, b; 
    double c;

    scanf("%d", &C);

    while (C--)
    {
        //input N: 노드수, M: edge수
        scanf("%d %d", &N, &M);


        // edge 입력
        for (int i = 0; i < M; i++)
        {
            scanf("%d %d %lf", &a, &b, &c);

            // a,b 중 작은 값을 n1에 입력하도록 했다. 
            if (a < b)
            {
                edges[i].n1 = a;
                edges[i].n2 = b;
            }
            else
            {
                edges[i].n1 = b;
                edges[i].n2 = a;
            }
            edges[i].w = c;
            edges[i].visit = false;
        }

        // 대칭 되는 edge도 만들어두기. a-b, b-a
        for (int i = M; i < M + M; i++)
        {
            edges[i].n1 = edges[i - M].n2;
            edges[i].n2 = edges[i - M].n1;
            edges[i].w = edges[i - M].w;
            edges[i].visit = false;
        }

        // edge 정렬. n1 크기 순으로
        merge_sort(0, M + M - 1);



        //모든 노드의 distance 큰 값으로 설정 뒤 힙트리에 PUSH

        int j,next=0;
        heap_end = 0;
        for (int i = 0; i < N; i++)
        {
            NODE node;
            node.distance = 9999999999.0;
            node.no = i;

            distance[i] = 9999999999.0;

            //해당 노드가 포함되는 edge의 edges배열에서 
            //시작 index와 끝 index 알아놓기
            int flag = 0;           
            for ( j = next; j < M + M; j++)
            {
                if (edges[j].n1 == i && flag == 0)
                {
                    node.start = j;
                    flag = 1;
                }
                else if (edges[j].n1 != i && flag == 1)
                {
                    node.end = j - 1;
                    next = j;
                    break;
                }
            }
            if (j == M + M) node.end = j - 1;

            push(node);

        }


        // 0번 노드의 distance를 1로 설정
        distance[0] = 1;
        // node의 distance가 바뀌었으므로, 
        //힙트리에서 노드 distance 바꾸고 위치 재설정
        edit(heap_idx[0], 1);
        //총 방문한 노드 수. 이제 1개 방문했음
        num_visit = 1;


        /////////////////////////////////////////////
        ///// Dijkstra

        int start, end;
        NODE min_node;

        while (1)
        {
            //힙트리에서 distance가 가장 작은 node를 pop
            min_node = pop(); 


            //해당 노드가 가지고 있는 edge들 하나하나씩 보면서 
            //min_node와 연결된 node들의 distance 바뀌는지 검사. 
            for (int i = min_node.start; i <= min_node.end; i++)
            {
                //이미 한번 봤던 edge는 pass
                if (edges[i].visit == true) continue;


                // EDGE=>  [min_node] <-> [ii] 
                int ii;
                if (min_node.no == edges[i].n1) ii = edges[i].n2;
                else ii = edges[i].n1;

                if (distance[min_node.no] * edges[i].w < distance[ii])
                {
                    distance[ii] = distance[min_node.no] * edges[i].w;
                    edit(heap_idx[ii], distance[ii]);
                }

                edges[i].visit = true;
            }

            num_visit++;
            if (num_visit == N) break;

        }
        printf("%.10f\n", distance[N - 1]);
    }
    return 0;
}