#include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <stdlib.h>

using namespace std;

int N; // 노드 수
int vertex; //간선의 수

int visit[10001] = { 0, };
long double res = 1; // 결과값
long double MIN_res = 1.7976931348623158e+308;
vector<long double> arr[10001];
stack<long double> s;
stack<long double> s_val;  //값 비교용 stack


/// 인접리스트 생성

/// 추가사항: 양방향 그래프 될 수 있도록 해주고, (  O ) 
///           자료형 double로 바꿔준다. ( O )

void input() {
    int node_a;
    int node_b;
    long double val;
    for (int i = 0; i < vertex; i++) {
        cin >> node_a >> node_b >> val;
        arr[node_a].push_back(node_b);
        arr[node_b].push_back(node_a);
        arr[node_a].push_back(val);
        arr[node_b].push_back(val);
    }

}

void DFS(int start) {

    if (start == N - 1) {  // 마지막노드에 도착하였다면.
        MIN_res = s_val.top();  //마지막노드까지 왔다는 것은, 최소의 값이라는 것을 의미하므로. 
        s_val.pop();
        return;
    }

    //들어오는 값 스택에 넣어주고
    s.push(start);

    // visit 해준다.
    visit[start] = 1;

    int temp_node = 0;

    for (int i = 0; i < arr[start].size(); i += 2) {

        temp_node = arr[start][i];  // 다음으로 갈 노드 

        if (!visit[temp_node] && (s_val.top()*arr[start][i+1])<MIN_res ) {  // 방문하지 않았고, 방문하지 않았다 하더라도 곱했을 경우 최소증폭보다 값이 크다면 X
            res = s_val.top()*arr[start][i + 1];
            s_val.push(res);
            DFS(temp_node);
        }
    }


    // 더이상 갈 곳이 없을때에는 pop해주려는 부분에 대해 visit 초기화 시켜주고, pop해준다.
    int temp = 0;
    temp = s.top();
    visit[temp] = 0;  
    s.pop();
    s_val.pop();



}


/// 초기화 함수
void init() {

    MIN_res = 1000000;
    for (int i = 0; i < N; i++) {
        visit[i] = 0;
    }

    // vector에서 사용한 동적메모리 해제
    for (int i = 0; i < N; i++) {
        arr[i].clear();
    }
}

void Test();
int main() {


    /// TestCase 입력
    int TestCase = 0;
    //freopen("in.txt", "r", stdin);
    cin >> TestCase;
    for (int i = 0; i < TestCase; i++) {

        /// 노드 수 입력
        cin >> N;

        /// 간선의 수 입력
        cin >> vertex;


        /// 간선정보 입력
        input();

        // Start : 0  , End : N-1 번
        /// DFS 
        s_val.push(1);  // 처음에 value 1 넣어주고 시작.
        DFS(0);

        cout.setf(ios::fixed);
        cout.precision(10);
        cout << MIN_res<<endl;
        init();
    }
    return 0;
}

/// Just Test
void Test() {


    // 인접리스트 출력
    for (int i = 0; i < vertex; i++) {
        cout << "시작:" << i << " ";
        for (int j = 0; j < arr[i].size(); j += 2) {
            cout << " 정점:" << arr[i][j] << " " << " 값:" << arr[i][j + 1] <<"/";
        }
        cout << endl;
    }
}

{{AD60Qx4D4IZyVpC0}}