void solve(){
    int n,m;
    cin>>n>>m;
    vector edg(n+10,vector<int>()),dis(n+10,vector<int>(n+10,-1e18));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edg[u].push_back(v);
        dis[u][v]=dis[v][u]=max(dis[u][v],w);
    }
    for(int i=1;i<=n;i++)dis[i][i]=0;

    vector<int> ans(n+10,-1e9);
    ans[1]=0;
    auto bfs=[&](){
        priority_queue<pll> q;
        q.push({0,1});
        while(q.size()){
            auto [val,u]=q.top();
            q.pop();
            for(auto v:edg[u]){
                if(ans[v]<ans[u]+dis[u][v]){
                    ans[v]=ans[u]+dis[u][v];
                    q.push({ans[v],v});
                }
            }
        }
    };

    bfs();
    if(ans[n]==-1e9)cout<<-1<<' ';
    else cout<<ans[n]<<' ';
    // for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    // cout<<'\n';
}

wa了好几发qaq