uses crt;
type a = array[0..500] of integer;
var paths : array[1..251] of ^a;
    smanji : array[1..251] of ^a;
    wght1, wght2, susunu : array[1..251] of integer;
    q : array[1..500] of record g, w, lst : integer; end;
    path, tmp, mojbroj, bpath : array[1..500] of integer;
    susj : array[1..500, 0..3] of record tko : integer; tezina : byte; end;
    bio : array[1..500] of boolean;
    bad : boolean;
    n, k, i, j, cur, l, novi, p, r, s, min : integer;
    f : text;

procedure solve (g, mwght : integer);
begin
  if mwght>=min then exit;

  if g>k then
     begin
     for i:=k+1 to n do if mojbroj[i]>=0 then exit;
     min:=mwght;
     bpath:=tmp;
     exit;
     end;

  bad:=False;
  if g>1 then
     if mojbroj[susunu[path[g]]]>0 then
        begin
        dec(mojbroj[susunu[path[g]]]);
        if mojbroj[susunu[path[g]]]<1 then bad:=True;
        end;

  inc (cur); tmp[cur]:=path[g+1];
  if not bad then solve (g+1, mwght+wght1[path[g]]);
  tmp[cur]:=0; dec (cur);

  if g>1 then
     if mojbroj[susunu[path[g]]]>=0 then
        inc (mojbroj[susunu[path[g]]]);


  bad:=False;

  for i:=1 to paths[path[g]]^[0] do
      begin
      if mojbroj[paths[path[g]]^[i]]<0 then bad:=True;
      mojbroj[paths[path[g]]^[i]]:=-mojbroj[paths[path[g]]^[i]];
      inc (cur); tmp[cur]:=paths[path[g]]^[i];
      end;

  for i:=1 to smanji[path[g]]^[0] do
      if mojbroj[smanji[path[g]]^[i]] > 0 then
         begin
         dec (mojbroj[smanji[path[g]]^[i]]);
         if mojbroj[smanji[path[g]]^[i]]=0 then bad:=True;
         end;

  if not bad then
     begin
     inc (cur); tmp[cur]:=path[g+1];
     solve (g+1, mwght+wght2[path[g]]);
     tmp[cur]:=0; dec(cur);
     end;

  for i:=1 to paths[path[g]]^[0] do
      begin
      mojbroj[paths[path[g]]^[i]]:=-mojbroj[paths[path[g]]^[i]];
      tmp[cur]:=0; dec (cur);
      end;

  for i:=1 to smanji[path[g]]^[0] do
      if mojbroj[smanji[path[g]]^[i]] >= 0 then
         inc (mojbroj[smanji[path[g]]^[i]]);
end;


procedure build_all_paths (g1, g2 : integer);
var i, j, l : integer;
begin
  fillchar (bio, 500, 0);
  i:=1; while susj[g1, i].tko<=k do inc(i);
  q[1].g:=susj[g1, i].tko; q[1].lst:=0; q[1].w:=susj[g1, i].tezina;
  cur:=1; novi:=1;

  while q[cur].g<>g2 do
    begin
    for i:=1 to 3 do
        if (not bio[susj[q[cur].g, i].tko]) and
           ((susj[q[cur].g, i].tko > k) or
            (susj[q[cur].g, i].tko = g2)) then
           begin
           inc (novi);
           q[novi].g:=susj[q[cur].g, i].tko;
           q[novi].lst:=cur;
           q[novi].w:=susj[q[cur].g, i].tezina+q[cur].w;
           bio[q[novi].g]:=True;
           end;
    inc (cur);
    end;

  i:=cur; j:=0; wght2[g1]:=q[i].w;
  while i>0 do begin inc (j); tmp[j]:=q[i].g; i:=q[i].lst; end;

  fillchar(bio, 500, 0);
  new (paths[g1]); new (smanji[g1]); smanji[g1]^[0]:=0;

  for i:=1 to j do begin paths[g1]^[i]:=tmp[j+1-i]; bio[tmp[i]]:=True; end;
  paths[g1]^[0]:=j-1;

  for i:=1 to j do
      for l:=1 to 3 do
          if (susj[tmp[i], l].tko>k) and
             (not bio[susj[tmp[i], l].tko]) then
             begin
             inc (smanji[g1]^[0]);
             smanji[g1]^[smanji[g1]^[0]]:=susj[tmp[i], l].tko;
             end;
end;


procedure build_path;
begin
  bio[1]:=True; path[1]:=1;

  for i:=1 to k-1 do
      begin
      j:=1;
      while (susj[path[i], j].tko>k) or (bio[susj[path[i], j].tko]) do inc(j);
      path[i+1]:=susj[path[i], j].tko;
      wght1[path[i]]:=susj[path[i], j].tezina;
      bio[path[i+1]]:=True;
      end;
end;


begin
  assign (f, 'CAV.IN'); reset (f);
  read (f, n, k);

  for i:=1 to 3*n div 2 do
      begin
      read (f, p, s, r);

      if (p<=k) and (s>k) then susunu[p]:=s;
      if (s<=k) and (p>k) then susunu[s]:=p;

      inc (susj[p, 0].tko);
      susj[p, susj[p, 0].tko].tko:=s;
      susj[p, susj[p, 0].tko].tezina:=r;

      inc (susj[s, 0].tko);
      susj[s, susj[s, 0].tko].tko:=p;
      susj[s, susj[s, 0].tko].tezina:=r;
      end;

  for i:=1 to n do mojbroj[i]:=2;

  build_path; path[k+1]:=1;
  for i:=1 to k do build_all_paths (path[i], path[i+1]);

  min:=32767; cur:=1; tmp[1]:=1;
  solve (1, 0);

  assign (f, 'CAV.OUT'); rewrite (f);
  for i:=1 to n do write (f, bpath[i], ' ');
  close (f);
end.