#define _USE_MATH_DEFINES #include using namespace std; //template #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() typedef long long int ll; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} //end typedef pair P; typedef pair T; int t,n,m; set

g[2010]; ll dijk(int u,int v){ ll dist[2010]; rep(i,0,n)dist[i]=INF; dist[u]=0; priority_queue,greater

> pq; pq.push({0,u}); while(!pq.empty()){ auto [d,x]=pq.top(); pq.pop(); if(dist[x]>t>>n>>m; vector es; rep(i,0,m){ int u,v,w; cin>>u>>v>>w; es.push_back({{u,v},w}); g[u].insert({v,w}); if(!t)g[v].insert({u,w}); } ll res=INF; for(auto [p,w]:es){ auto [u,v]=p; g[u].erase({v,w}); if(!t)g[v].erase({u,w}); chmin(res,dijk(v,u)+w); g[u].insert({v,w}); if(!t)g[v].insert({u,w}); } if(res==INF)puts("-1"); else cout<