#include<bits/stdc++.h>
using namespace std;
struct edge{
int connect;
int price;
};
int dijsktra(vector<edge> al[], int source, int target, int c){
vector<int> min_dis(c+1, INT_MAX);
min_dis[source] = 0;
set< pair<int, int> > active_vertices;
active_vertices.insert(make_pair(0, source));
while(!active_vertices.empty()){
int where = active_vertices.begin()->second;
if(where==target){
return min_dis[where];
}
active_vertices.erase(active_vertices.begin());
for(int i=0; i<al[where].size(); i++){
if(min_dis[al[where][i].connect] > min_dis[where]+al[where][i].price){
active_vertices.erase({min_dis[al[where][i].connect], al[where][i].connect});
min_dis[al[where][i].connect] = min_dis[where]+al[where][i].price;
active_vertices.insert(make_pair(min_dis[al[where][i].connect], al[where][i].connect));
}
}
}
return -1;
}
int main(){
int c, f;
cin >> c >> f;
vector<edge> al[c+1];
for(int i=0; i<f; i++){
int x;
edge t;
cin >> x >> t.connect >> t.price;
al[x].push_back(t);
}
vector<int> cheap;
for(int i=1; i<=c; i++){
for(int j=1; j<=c; j++){
if(i!=j)
cheap.push_back(dijsktra(al, i, j, c));
}
}
cout << *max_element(cheap.begin(), cheap.end());
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBlZGdlewogICAgaW50IGNvbm5lY3Q7CiAgICBpbnQgcHJpY2U7Cgp9OwoKaW50IGRpanNrdHJhKHZlY3RvcjxlZGdlPiBhbFtdLCBpbnQgc291cmNlLCBpbnQgdGFyZ2V0LCBpbnQgYyl7CiAgICB2ZWN0b3I8aW50PiBtaW5fZGlzKGMrMSwgSU5UX01BWCk7CiAgICBtaW5fZGlzW3NvdXJjZV0gPSAwOwoKICAgIHNldDwgcGFpcjxpbnQsIGludD4gPiBhY3RpdmVfdmVydGljZXM7CiAgICBhY3RpdmVfdmVydGljZXMuaW5zZXJ0KG1ha2VfcGFpcigwLCBzb3VyY2UpKTsKCiAgICB3aGlsZSghYWN0aXZlX3ZlcnRpY2VzLmVtcHR5KCkpewogICAgICAgIGludCB3aGVyZSA9IGFjdGl2ZV92ZXJ0aWNlcy5iZWdpbigpLT5zZWNvbmQ7CiAgICAgICAgaWYod2hlcmU9PXRhcmdldCl7CiAgICAgICAgICAgIHJldHVybiBtaW5fZGlzW3doZXJlXTsKICAgICAgICB9CiAgICAgICAgYWN0aXZlX3ZlcnRpY2VzLmVyYXNlKGFjdGl2ZV92ZXJ0aWNlcy5iZWdpbigpKTsKICAgICAgICBmb3IoaW50IGk9MDsgaTxhbFt3aGVyZV0uc2l6ZSgpOyBpKyspewogICAgICAgICAgICBpZihtaW5fZGlzW2FsW3doZXJlXVtpXS5jb25uZWN0XSA+IG1pbl9kaXNbd2hlcmVdK2FsW3doZXJlXVtpXS5wcmljZSl7CiAgICAgICAgICAgICAgICBhY3RpdmVfdmVydGljZXMuZXJhc2Uoe21pbl9kaXNbYWxbd2hlcmVdW2ldLmNvbm5lY3RdLCBhbFt3aGVyZV1baV0uY29ubmVjdH0pOwogICAgICAgICAgICAgICAgbWluX2Rpc1thbFt3aGVyZV1baV0uY29ubmVjdF0gPSBtaW5fZGlzW3doZXJlXSthbFt3aGVyZV1baV0ucHJpY2U7CiAgICAgICAgICAgICAgICBhY3RpdmVfdmVydGljZXMuaW5zZXJ0KG1ha2VfcGFpcihtaW5fZGlzW2FsW3doZXJlXVtpXS5jb25uZWN0XSwgYWxbd2hlcmVdW2ldLmNvbm5lY3QpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAtMTsKfQoKaW50IG1haW4oKXsKICAgIGludCBjLCBmOwogICAgY2luID4+IGMgPj4gIGY7CiAgICB2ZWN0b3I8ZWRnZT4gYWxbYysxXTsKICAgIGZvcihpbnQgaT0wOyBpPGY7IGkrKyl7CiAgICAgICAgaW50IHg7CiAgICAgICAgZWRnZSB0OwogICAgICAgIGNpbiA+PiB4ID4+IHQuY29ubmVjdCA+PiB0LnByaWNlOwogICAgICAgIGFsW3hdLnB1c2hfYmFjayh0KTsKICAgIH0KICAgIHZlY3RvcjxpbnQ+IGNoZWFwOwogICAgZm9yKGludCBpPTE7IGk8PWM7IGkrKyl7CiAgICAgICAgZm9yKGludCBqPTE7IGo8PWM7IGorKyl7CiAgICAgICAgICAgIGlmKGkhPWopCiAgICAgICAgICAgIGNoZWFwLnB1c2hfYmFjayhkaWpza3RyYShhbCwgaSwgaiwgYykpOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQgPDwgKm1heF9lbGVtZW50KGNoZWFwLmJlZ2luKCksIGNoZWFwLmVuZCgpKTsKfQo=