#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <vector>
#include <queue>

using namespace std;

struct Hrana {
  int u;	// počáteční vrchol
  int v;	// koncový vrchol
  int c;	// kapacita hrany
  int f;	// průtok hranou
};

int opacna(int index) {
  return (index%2==0)?(index+1):(index-1);
}

int Ford_Fulkerson(vector<int> graf[], int N, vector<Hrana> &hrana, int S, int T) {
  queue<int> q;			// pro procházení do šířky
  int prichozi[N];		// hrana po které jsme přišli
  int max_tok = 0;

  do {
    int min_rezerva = INT_MAX;
    // inicializace příchodů
    for (int i=0; i<N; i++)
      prichozi[i] = -1;
    while(!q.empty())
      q.pop();
    // procházení do šířky
    prichozi[S] = -2;
    q.push(S);
    int akt;
    while(prichozi[T]==-1 && !q.empty()) {
      akt = q.front();
      q.pop();
      for (vector<int>::iterator i = graf[akt].begin(); i != graf[akt].end(); i++) {
	int index = *i;
	int opak = opacna(index);
	int rezerva = hrana[index].c - hrana[index].f + hrana[opak].f;
	// při nenulové rezervě přidáme do fronty
	if (rezerva>0 && prichozi[hrana[index].v]==-1) {
	  prichozi[hrana[index].v] = index;
	  q.push(hrana[index].v);
	}
      }
    }
    // nalezení minimální rezervy, pokud existuje
    akt = T;
    while(prichozi[akt]>=0) {
      int index = prichozi[akt];
      int opak = opacna(index);
      int rezerva = hrana[index].c - hrana[index].f + hrana[opak].f;
      min_rezerva = min(min_rezerva, rezerva);
      akt = hrana[index].u;
    }
    // úprava toků hran
    akt = T;
    while(prichozi[akt]>=0) {
      int index = prichozi[akt];
      int opak = opacna(index);
      if (hrana[index].f + min_rezerva <= hrana[index].c)
	hrana[index].f += min_rezerva;
      else {
	hrana[opak].f -= min_rezerva;
	if (hrana[opak].f < 0) {
	  hrana[index].f += -hrana[opak].f;
	  hrana[opak].f = 0;
	}
      }
      akt = hrana[index].u;
    }
    if (prichozi[T]!=-1)
      max_tok += min_rezerva;
  } while(prichozi[T]!=-1);

  return max_tok;
}

int N, M;	// počet vrcholů a hran
vector<int> graf[2000];
vector<Hrana> hrana;

int main() {
  scanf("%d%d", &N, &M);
  /* vrchol 0 je zdroj, vrchol 2*N+2 stok
   * vrcholy si rovnou při načítání podrozdělujeme na levé a pravé
   * liché vrcholy budou levé a sudé vrcholy k nim odpovídající pravé
   * Ke každé hraně přidáváme i její opačnou hranu.
   */
  int zdroj = 0, stok = 2*N+2;
  Hrana h; int suma = 0;
  for (int i=1; i<=N; i++) {
    int max, min;
    scanf("%d%d", &min, &max);
    h = (Hrana){zdroj, 2*i, max, 0}; hrana.push_back(h);
    h = (Hrana){2*i, zdroj, 0, 0}; hrana.push_back(h);
    graf[zdroj].push_back(hrana.size()-2);
    graf[2*i].push_back(hrana.size()-1);
    h = (Hrana){2*i+1, stok, min, 0}; hrana.push_back(h);
    h = (Hrana){stok, 2*i+1, 0, 0}; hrana.push_back(h);
    graf[2*i+1].push_back(hrana.size()-2);
    graf[stok].push_back(hrana.size()-1);
    suma += min;
  }
  /* Načtení hran + opačných.
   * Rozmyslete si, proč nemusíme kontrolovat, zda opačná hrana taky není na vstupu.
   */
  int K = hrana.size();		// index, kterým začínají hrany uvnitř grafu
  for (int i=0; i<M; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    h = (Hrana){2*u, 2*v+1, c, 0}; hrana.push_back(h);
    h = (Hrana){2*v+1, 2*u, 0, 0}; hrana.push_back(h);
    graf[2*u].push_back(hrana.size()-2);
    graf[2*v+1].push_back(hrana.size()-1);
  }
  // zavoláme maximální tok
  int max_tok = Ford_Fulkerson(graf, 2*N+3, hrana, zdroj, stok);
  // vypíšeme výsledek
  if (max_tok!=suma)
    printf("Neexistuje žádné řešení.\n");
  else {
    printf("Hrany budou následující toky: (u, v, c, f)\n");
    for (int i=K; i<hrana.size(); i+=2)
      printf("%d %d %d %d\n", hrana[i].u/2, hrana[i].v/2, hrana[i].c, hrana[i].f);
  }
  return 0;
}