BZOJ1509 NOI2003 Hookey

{$INLINE ON}
program bzoj1509_1;
 
const size=3;
 
type tnode=record
        n,w,next:longint;
     end;
     inta=array[1..size] of int64;
 
const maxn=200017;
 
var g,q,p,pe,son:array[0..maxn] of longint;
    v,flag:array[0..maxn] of boolean;
    d:array[0..maxn] of inta;
    od:array[0..maxn] of int64;
    mem:array[0..maxn*2] of tnode;
    n,m,memsize,frt,rer:longint;
 
function max(i,j:int64):int64; inline; begin if i>j then exit(i) else exit(j); end;
 
procedure insnbs(u,v,iw:longint); inline;
begin
inc(memsize); with mem[memsize] do begin n:=v; w:=iw; next:=g[u]; end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin n:=u; w:=iw; next:=g[v]; end; g[v]:=memsize;
end;
 
procedure insert(var s:inta;v:int64); inline;
var i:longint;
begin
for i:=1 to size do if v>s[i] then begin
        if i<size then move(s[i],s[i+1],(size-i)<<3); s[i]:=v; break;
end;
end;
 
function dp(u:longint):int64;
var head,tail,t1,i,j:longint;
    k:int64;
begin
fillchar(d,sizeof(d),0); fillchar(v,sizeof(v),0); frt:=0; rer:=1; q[rer]:=u; v[u]:=true;
while frt<rer do begin inc(frt); head:=q[frt];
        t1:=g[head]; while t1<>0 do begin tail:=mem[t1].n;
                if not v[tail] then begin
                        inc(rer); q[rer]:=tail; v[tail]:=true; p[tail]:=head; pe[tail]:=t1;
                end; t1:=mem[t1].next;
        end;
end; for j:=rer downto 2 do begin i:=q[j]; k:=d[i][1]+mem[pe[i]].w;
        if k>d[p[i]][1] then son[p[i]]:=i; insert(d[p[i]],k);
end; for i:=1 to n do flag[son[i]]:=true; fillchar(od,sizeof(od),0); for j:=2 to rer do begin
        i:=q[j]; od[i]:=max(od[p[i]],d[p[i]][1+byte(flag[i])])+mem[pe[i]].w;
end; for i:=1 to n do insert(d[i],od[i]); dp:=0; for i:=1 to n do dp:=max(dp,d[i][1]+d[i][2]<<1+d[i][3]);
end;
 
procedure init;
var i,j,u,v,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1; fillchar(flag,sizeof(flag),0);
readln(n,m); for i:=1 to m do begin readln(u,v,w); insnbs(u,v,w); end;
end;
 
begin
init;
writeln(dp(1));
end.