{$MODE OBJFPC}
program SmartDogContest;
const
InputFile = '';
OutputFile = '';
maxN = 1000;
maxM = 10000;
maxW = 1000000000;
maxD = (maxN + 1) * maxW;
type
TEdge = record
u, v, c: Integer;
end;
var
fi, fo: TextFile;
e: array[1..maxM] of TEdge;
d: array[1..maxN + 1, 1..maxN] of Int64;
n, m: Integer;
BestMiu: Extended;
procedure Enter;
var
i: Integer;
begin
ReadLn(fi, n, m);
for i := 1 to m do
with e[i] do
ReadLn(fi, u, v, c);
end;
procedure Init;
var
i: Integer;
begin
FillQWord(d, SizeOf(d) div 8, maxD);
for i := 1 to n do
d[1, i] := 0;
end;
procedure Minimize(var target: Int64; value: Int64); inline;
begin
if target > value then target := value;
end;
procedure Optimize;
var
k, i: Integer;
begin
for k := 2 to n + 1 do //Tinh d[k, v] qua cac d[k - 1, u]
for i := 1 to m do
with e[i] do
Minimize(d[k, v], d[k - 1, u] + c);
end;
procedure GetBest;
var
v, k: Integer;
min, max, trial: Extended;
begin
min := maxD;
for v := 1 to n do
if d[n + 1, v] < maxD then
begin
max := -maxD;
for k := 1 to n do
if d[k, v] < maxD then
begin
trial := (d[n + 1, v] - d[k, v]) / (n - k + 1);
if max < trial then max := trial;
end;
if max < min then
min := max;
end;
BestMiu := min;
end;
begin
AssignFile(fi, InputFile); Reset(fi);
AssignFile(fo, OutputFile); Rewrite(fo);
try
Enter;
Init;
Optimize;
GetBest;
if BestMiu = maxD then
Write(fo, 'NO TOUR')
else
Write(fo, BestMiu:0:2);
finally
CloseFile(fi); CloseFile(fo);
end;
end.
eyRNT0RFIE9CSkZQQ30KcHJvZ3JhbSBTbWFydERvZ0NvbnRlc3Q7CmNvbnN0CiAgSW5wdXRGaWxlICA9ICcnOwogIE91dHB1dEZpbGUgPSAnJzsKICBtYXhOID0gMTAwMDsKICBtYXhNID0gMTAwMDA7CiAgbWF4VyA9IDEwMDAwMDAwMDA7CiAgbWF4RCA9IChtYXhOICsgMSkgKiBtYXhXOwp0eXBlCiAgVEVkZ2UgPSByZWNvcmQKICAgIHUsIHYsIGM6IEludGVnZXI7CiAgZW5kOwp2YXIKICBmaSwgZm86IFRleHRGaWxlOwogIGU6IGFycmF5WzEuLm1heE1dIG9mIFRFZGdlOwogIGQ6IGFycmF5WzEuLm1heE4gKyAxLCAxLi5tYXhOXSBvZiBJbnQ2NDsKICBuLCBtOiBJbnRlZ2VyOwogIEJlc3RNaXU6IEV4dGVuZGVkOwogCnByb2NlZHVyZSBFbnRlcjsKdmFyCiAgaTogSW50ZWdlcjsKYmVnaW4KICBSZWFkTG4oZmksIG4sIG0pOwogIGZvciBpIDo9IDEgdG8gbSBkbwogICAgd2l0aCBlW2ldIGRvCiAgICAgIFJlYWRMbihmaSwgdSwgdiwgYyk7CmVuZDsKIApwcm9jZWR1cmUgSW5pdDsKdmFyCiAgaTogSW50ZWdlcjsKYmVnaW4KICBGaWxsUVdvcmQoZCwgU2l6ZU9mKGQpIGRpdiA4LCBtYXhEKTsKICBmb3IgaSA6PSAxIHRvIG4gZG8KICAgIGRbMSwgaV0gOj0gMDsKZW5kOwogCnByb2NlZHVyZSBNaW5pbWl6ZSh2YXIgdGFyZ2V0OiBJbnQ2NDsgdmFsdWU6IEludDY0KTsgaW5saW5lOwpiZWdpbgogIGlmIHRhcmdldCA+IHZhbHVlIHRoZW4gdGFyZ2V0IDo9IHZhbHVlOwplbmQ7CiAKcHJvY2VkdXJlIE9wdGltaXplOwp2YXIKICBrLCBpOiBJbnRlZ2VyOwpiZWdpbgogIGZvciBrIDo9IDIgdG8gbiArIDEgZG8gLy9UaW5oIGRbaywgdl0gcXVhIGNhYyBkW2sgLSAxLCB1XQogICAgZm9yIGkgOj0gMSB0byBtIGRvCiAgICAgIHdpdGggZVtpXSBkbwogICAgICAgIE1pbmltaXplKGRbaywgdl0sIGRbayAtIDEsIHVdICsgYyk7CmVuZDsKIApwcm9jZWR1cmUgR2V0QmVzdDsKdmFyCiAgdiwgazogSW50ZWdlcjsKICBtaW4sIG1heCwgdHJpYWw6IEV4dGVuZGVkOwpiZWdpbgogIG1pbiA6PSBtYXhEOwogIGZvciB2IDo9IDEgdG8gbiBkbwogICAgaWYgZFtuICsgMSwgdl0gPCBtYXhEIHRoZW4KICAgICAgYmVnaW4KICAgICAgICBtYXggOj0gLW1heEQ7CiAgICAgICAgZm9yIGsgOj0gMSB0byBuIGRvCiAgICAgICAgICBpZiBkW2ssIHZdIDwgbWF4RCB0aGVuCiAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgdHJpYWwgOj0gKGRbbiArIDEsIHZdIC0gZFtrLCB2XSkgLyAobiAtIGsgKyAxKTsKICAgICAgICAgICAgICBpZiBtYXggPCB0cmlhbCB0aGVuIG1heCA6PSB0cmlhbDsKICAgICAgICAgICAgZW5kOwogICAgICAgIGlmIG1heCA8IG1pbiB0aGVuCiAgICAgICAgICBtaW4gOj0gbWF4OwogICAgICBlbmQ7CiAgQmVzdE1pdSA6PSBtaW47CmVuZDsKIApiZWdpbgogIEFzc2lnbkZpbGUoZmksIElucHV0RmlsZSk7IFJlc2V0KGZpKTsKICBBc3NpZ25GaWxlKGZvLCBPdXRwdXRGaWxlKTsgUmV3cml0ZShmbyk7CiAgdHJ5CiAgICBFbnRlcjsKICAgIEluaXQ7CiAgICBPcHRpbWl6ZTsKICAgIEdldEJlc3Q7CiAgICBpZiBCZXN0TWl1ID0gbWF4RCB0aGVuCiAgICAgIFdyaXRlKGZvLCAnTk8gVE9VUicpCiAgICBlbHNlCiAgICAgIFdyaXRlKGZvLCBCZXN0TWl1OjA6Mik7CiAgZmluYWxseQogICAgQ2xvc2VGaWxlKGZpKTsgQ2xvc2VGaWxlKGZvKTsKICBlbmQ7CmVuZC4=