#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int tc;


#define pp pair<int,int>
using namespace std;
struct pri
{
    int operator() (const pair<int,int>&p1,const pair<int,int>&p2)
    {
        return p1.second<p2.second;
    }
}p;

int main() {
    //freopen("test.inp", "r", stdin);
    scanf("%d", &tc);
    while (tc --) {
        int n, m;
        priority_queue<pp,vector<pp>,pri> q;
        cin>>n >> m;
        vector<pp> g[n+1];
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            cin>>u>>v>>w;
            g[u].push_back(pp(v,w));
            g[v].push_back(pp(u,w));
        }
        int s = 1;
        int d[n+1];
        for(int i=1;i<=n;i++)
            d[i]=999999;
        d[s]=0;
        q.push(pp(s,d[s]));
        while(!q.empty())
        {
            u=q.top().first;
            q.pop();
            int size=g[u].size();
            for(int i=0;i<size;i++)
            {
                v=g[u][i].first;
                w=g[u][i].second;
                if(d[v]>d[u]+w)
                {
                    d[v]=d[u]+w;
                    q.push(pp(v,d[v]));
                }
            }
        }
        int rs = 0;
        for(int i=1;i<=n;i++) {
            rs = max(rs, d[i] - d[i - 1]);
        }
        printf("%d\n", rs);
    }
    return 0;
}