#include <stdio.h>
//#include <time.h>

#define NUM 10000

int C;
int NN; // number of computers ; NN <= NUM
int edge;   // 최대 20000 개
float g[NUM][NUM];  // 배열로 잡을 수 있는 크기는? 10억까지는 괜찮음..
float result;
float max;

float dijkstra(int src, int dest)
{
    int N[NUM];
    int Ni = 0;
    float d[NUM];
    int p[NUM];

    float low = max;
    int lowi = -1;

    // init & set d[]
    N[src] = 1;
    Ni = 1;
    for(int i=0;i<dest;i++) {
        d[i] = g[src][i];
        p[i] = -1;
    }

    while(Ni<NUM) { // dest ??
        /* 여기서 선언하면 NUM 이 큰 경우 죽는다..??? */
        //float low = max;
        //int lowi = -1;

        // find shortest path
        for(int i=0;i<dest;i++) {
            if(d[i] != -1 && d[i] != 0 && N[i] != 1 && low > d[i]) {
                low = d[i];
                lowi = i;
            }
        }
        N[lowi] = 1;
        Ni++;

        // update shortest path
        for(int i=0;i<dest;i++) {
            if(g[lowi][i] != -1 && g[lowi][i] != 0 && N[i] != 1) {
                if(d[i] == -1 || d[i] == 0 || d[i] > d[lowi] * g[lowi][i]) {
                    d[i] = d[lowi] * g[lowi][i];
                    p[i] = lowi;
                }
            }
        }
    }

    return d[dest-1];
}

int main(void)
{
    //clock_t st = clock();

    //freopen("input2.txt", "r", stdin);
    //setbuf(stdout, NULL);

    scanf("%d",&C);
    for(int i=0;i<C;i++)
    {
        scanf("%d %d", &NN, &edge);

        // init matrix
        for(int j=0;j<NUM;j++) {
            for(int k=0;k<NUM;k++) {
                g[j][k] = -1;
            }
            g[j][j] = 0;
        }

        max = 0;    // to find max edge

        // make matrix
        for(int j=0;j<edge;j++) {
            int x, y;
            float w;
            scanf("%d %d %f", &x, &y, &w);

            if(max < w)
                max = w;

            if(g[x][y] == -1 || (g[x][y] != -1 && g[x][y] > w))
                g[x][y] = g[y][x] = w;
        }

        max = max + 1;

        if(NN == 0 || NN == 1)
            result = 0;
        else
            result = dijkstra(0, NN);

        printf("%.10f\n", result);
    }   

    //printf("time : %d\n",clock()-st);

    return 0;
}