var
 re:array[1..1000,1..2]of longint;
 map,f:array[1..1000,1..1000]of longint;
 a:array[1..20000]of longint;
 v:array[1..1000]of boolean;
 head,tail,x:longint;
 n,m,j,i,k,b,ans,s,t:longint;
 flag:boolean;

 procedure tiao;
 var i,fa,x:longint;
 begin
   i:=n;
   x:=re[i,2];
   fa:=re[i,1];
   repeat
     if fa>0 then
       begin
         f[fa,i]:=f[fa,i]+x;
         i:=fa;
         fa:=re[i,1];
       end
     else
       begin
          fa:=-fa;
          f[i,fa]:=f[i,fa]-x;
          i:=fa;
          fa:=re[i,1];
       end;
   until(i=1);
 end;

 function min(a,b:longint):longint;
  begin if a<b then exit(a) else exit(b);end;

 procedure bfs;
  var i:longint;
  begin
    fillchar(v,sizeof(v),0);
    v[1]:=true;
    head:=0;tail:=1;a[1]:=1;
    re[1,1]:=1;re[1,2]:=maxlongint;

    repeat
      inc(head);
      x:=a[head];
      for i:=1 to n do
       if v[i]=false then
        begin
            if (map[x,i]>f[x,i])then
              begin
                v[i]:=true;re[i,1]:=x;re[i,2]:=min(re[x,2],map[x,i]-f[x,i]);
                inc(tail);a[tail]:=i;
                if i=n then begin tiao;flag:=true;exit;end;
              end;

            if (map[i,x]>0)and(f[i,x]>0)then
              begin
                v[i]:=true;re[i,1]:=-x;re[i,2]:=min(re[x,2],f[i,x]);
                inc(tail);a[tail]:=i;
                if i=n then begin tiao;flag:=true;exit;end;
              end;
        end;

    until head>=tail;

  end;



begin
assign(input,'defence.in');reset(input);
assign(output,'defence.out');rewrite(output);
  readln(n,m,s,t);
  for i:=1 to m do
   begin
    readln(j,k,b);b:=b*(n+1);
    map[j,k]:=b;map[k,j]:=b;
   end;

  repeat
   flag:=false;
   bfs;
  until flag=false;

 for i:=1 to n-1 do ans:=ans+f[i,n];

 writeln(ans mod n);
 close(input);close(output);
end.