spfa写法（数据小，代码好写，预处理结束后for一遍检查是都全部访问并更新答案即可。）

#include <bits/stdc++.h>
#define sz(a, b) ((a + b - 1) / b)
#define all(_) _.begin(), _.end()
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;
using u32 = uint32_t;
const int N = 110, M = 210, INF = 0x3f3f3f3f;
struct edge { int to; int w; int nxt; } e[M << 1];
int n, m, idx;
int dist[N], h[N];
bitset<N> vis;
void add(int a, int b, int c) {
  e[idx] = {b, c, h[a]};
  h[a] = idx++;
}

int spfa() {
  int ans = 0;
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  queue<int> q;
  q.push(1);
  ans = max(ans, dist[1]);
  vis[1] = true;
  while(q.size()) {
    int t = q.front();
    q.pop();
    vis[t] = false;
    for(int i = h[t]; ~i ;i = e[i].nxt) {
      int j = e[i].to, w = e[i].w;
      if(dist[j] > dist[t] + w) {
        dist[j] = dist[t] + w;
        if(!vis[j]) {
          q.push(j);
          vis[j] = true;
        }
      }
    }
  }
  for(int i = 1; i <= n; i ++) {
    if(dist[i] == INF) return -1;
    ans = max(ans, dist[i]);
  }
  return ans;
}
int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  memset(h, -1, sizeof h);
  cin >> n >> m;
  for(; m --; ) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
    add(b, a, c);
  } 
  int t = spfa();
  cout << t << "\n";
}