记录编号	23611	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]旅行	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	Pascal	运行时间	0.260 s
提交时间	2011-03-16 13:36:03	内存使用	2.42 MiB

program toura;
type
	s=record
		key:longint;
		next:longint;
		p:extended;
	end;
var
	i,j,k,l,n,m:longint;
	a:array[0..60000]of s;
	f:array[-1..100000]of longint;
	min:array[0..10000]of extended;
	o:longint;
	t:extended;
	
procedure insert(const x,y,z:longint);
begin
	if a[x].key=0 then
	begin
		a[x].key:=y;
		a[x].p:=z/100;
	end
	else
	begin
		inc(o);
		a[o].key:=y;
		a[o].p:=z/100;
		a[o].next:=a[x].next;
		a[x].next:=o;
	end;
end;

begin
	assign(input,'toura.in');
	reset(input);
	assign(output,'toura.out');
	rewrite(output);
	
	readln(n,m);
	o:=n;
	
	for i:=1 to m do
	begin
		readln(j,k,l);
		insert(j,k,l);
		insert(k,j,l)
	end;
	
	for i:=1 to n do
		min[i]:=0;
	min[1]:=1;
	
	f[0]:=1;
	f[1]:=1;
	i:=1;
	
	while i<=f[0] do
	begin
		j:=f[i];
		while a[j].key<>0 do
		begin
			t:=min[f[i]]*a[j].p;
			if t>min[a[j].key] then
			begin
				min[a[j].key]:=t;
				inc(f[0]);
				f[f[0]]:=a[j].key;
			end;
			j:=a[j].next;
		end;
		inc(i);
	end;
	
	writeln(min[n]*100:0:6);
	
	close(input);
	close(output);
end.