// Simple solution to assignment problem,
// AKA minimum weighted bipartite matching, using Floyd-Warshall
// to find negative-weight cycle to decrease cost.
// Slower (O(n**4) than Hungarian method (O(m*m*n)).
// May 26, 2007 BPW

// Note:  Internally the left column is padded with vertices so
// the two columns have the same number of vertices.

#include <stdio.h>
#include <stdlib.h>

#define oo (999999) // infinity

int m,n;               // Number of left column and right column vertices
int inWeight[50][50];  // Input weights
int perm[50];

// Uses 0..n-1 for left column vertices, n..2*n-1 for right column vertices
int FW[100][100],succ[100][100];  // For Floyd-Warshall

void readInput()
{
int left,right,weight;

scanf("%d %d",&m,&n);
if (m>n)
  exit(0);

for (left=0;left<n;left++)
  for (right=0;right<n;right++)
    inWeight[left][right]=oo;

while (1)
{
  scanf("%d %d %d",&left,&right,&weight);
  if (left==(-1))
    break;
  if (left<0 || left>=m || right<0 || right>=n || weight<0 || weight>=oo)
    exit(0);
  if (weight<inWeight[left][right])
    inWeight[left][right]=weight;
}
}

void floydWarshall()
{
int i,j,k,left,right;

// Load matrices for Floyd-Warshall
for (i=0;i<n+n;i++)
  for (j=0;j<n+n;j++)
  {
    FW[i][j]=oo;
    succ[i][j]=j;
  }

// Record edges based on present matching
for (left=0;left<n;left++)
{
  for (right=0;right<n;right++)
    if (right!=perm[left])
      FW[left][n+right]=inWeight[left][right];  // Allows edge to be included
  // Allows edge to be removed
  FW[n+perm[left]][left]=(-inWeight[left][perm[left]]);
}

// Floyd-Warshall, with successors

for (j=0;j<n+n;j++)
  for (i=0;i<n+n;i++)
    for (k=0;k<n+n;k++)
    {
      int newFW=FW[i][j]+FW[j][k];
      if (newFW<FW[i][k])
      {
        FW[i][k]=newFW;
        succ[i][k]=succ[i][j];
      }
    }
}

int findNegativeCycle()
{
// Search diagonal for negative cycle starting in left column
int negCycleIndex;

for (negCycleIndex=0;
     negCycleIndex<n && FW[negCycleIndex][negCycleIndex]>=0;
     negCycleIndex++)
  ;
return negCycleIndex;
}

int findInnermostCycle(int negCycleIndex)
{
// Find innermost cycle, just in case there are nested negative cycles.
int left,right,i;
int cycleCheck[50];

for (i=0;i<n;i++)
  cycleCheck[i]=0;
cycleCheck[negCycleIndex]=1;
right=succ[negCycleIndex][negCycleIndex];  // right is in right column
while (1)
{
  left=succ[right][negCycleIndex];  // left is in left column
  if (cycleCheck[left])  // Been here before, j is in innermost negative cycle
    break;
  cycleCheck[left]=1;
  right=succ[left][negCycleIndex];
}
if (negCycleIndex!=left)
  printf("Changed start of cycle from %d to %d\n",negCycleIndex,left);
return left;
}

void updateMatching(int negCycleIndex)
{
// Update matching by going around the cycle.
int left,right;

left=negCycleIndex;
right=succ[negCycleIndex][negCycleIndex];
while (1)
{
  // Newly included edge
  printf("left is %d, right is %d weight %d\n",
    left,right-n,inWeight[left][right-n]);
  perm[left]=right-n;
  left=succ[right][negCycleIndex];
  // Removed edge
  printf("right is %d, left is %d weight %d\n",
    right-n,left,-inWeight[left][right-n]);
  if (left==negCycleIndex)
    break;
  right=succ[left][negCycleIndex];
}
}

main()
{
int i;
int sum,ooCount;

readInput();

// Initial matching - left column i to right column i
for (i=0;i<n;i++)
  perm[i]=i;

while (1)
{
  // In each round a negative-weight cycle is found
  // and the matching is changed.
  sum=ooCount=0;
  for (i=0;i<n;i++)
    if (inWeight[i][perm[i]]==oo)
      ooCount++;
    else
      sum+=inWeight[i][perm[i]];
  printf("Present matching weight is %d with %d unmatched right vertices\n",
    sum,ooCount);

  floydWarshall();

  int negCycleIndex=findNegativeCycle();

  if (negCycleIndex==n)
    break;  // Improvement is not possible

  printf("negCycleIndex is %d\n",negCycleIndex);

  negCycleIndex=findInnermostCycle(negCycleIndex);

  updateMatching(negCycleIndex);
}

printf("Final matching is:\n");
sum=0;
for (i=0;i<m;i++)
  if (inWeight[i][perm[i]]<oo)
  {
    printf("%d %d %d\n",i,perm[i],inWeight[i][perm[i]]);
    sum+=inWeight[i][perm[i]];
  }
printf("Weight is %d\n",sum);
}