#include <bits/stdc++.h>
using namespace std;
class Graph_func {
 public:
  bool graph_from1 = true;
  bool graph_tree = false;
  bool graph_weight = false;
  bool graph_digraph = false;
  int Vnum;
  int Enum;
  vector<pair<int, int> > edgelist;
  vector<long long> edgeweight;
  vector<vector<int> > adjlist;
  vector<vector<long long> > adjlistweight;
  vector<int> adjnum;
  vector<int> adj_to_root;
  vector<int> DP;
  vector<int> vlist_from_root;
  vector<long long> xdist;
  vector<bool> x_visited;
  vector<int> x_prqarr;
  vector<bool> x_filled;
  vector<bool> BW;
  vector<long long> lenall;
  void read_edge();
  void read_edge_array();
  void adjini();
  void visited_ini();
  void adjsort();
  vector<bool> graph_num_BFS(int BFS_ini, vector<bool> filled);
  int graph_num();
  void graph_BFS(long long BFS_ini);
  void graph_DFS(long long DFS_ini);
  void xydist_tree(int x);
  void xydist(int x);
  vector<pair<int, int> > D;
  long long diameter();
  void ReRooting(long long root);
  Graph_func Kruskal();
  int dim_num(int dim);
  void solve();
  bool xydist_def = false;
};
class UnionFind {
 public:
  vector<int> par;
  vector<int> adjnum;
  int N;
  void UnionFind_ini(int Narg);
  int root(int x);
  void unite(int x, int y);
  bool same(int x, int y);
  int adjnum_func(int x);
};
void UnionFind::UnionFind_ini(int Narg) {
  N = Narg;
  adjnum.resize(N);
  par.resize(N);
  for (int(i) = 0; (i) < (N); (i)++) {
    adjnum[i] = 1;
    par[i] = i;
  }
}
int UnionFind::root(int x) {
  if (par[x] == x) return x;
  par[x] = root(par[x]);
  return par[x];
}
void UnionFind::unite(int x, int y) {
  int rx = root(x);
  int ry = root(y);
  if (rx == ry) return;
  par[rx] = ry;
  adjnum[ry] += adjnum[rx];
  return;
}
bool UnionFind::same(int x, int y) {
  int rx = root(x);
  int ry = root(y);
  return rx == ry;
}
int UnionFind::adjnum_func(int x) {
  int rx = root(x);
  return adjnum[rx];
}
void Graph_func::read_edge() {
  cin >> Vnum;
  if (graph_tree)
    Enum = Vnum - 1;
  else
    cin >> Enum;
  edgelist.resize(Enum);
  edgeweight.resize(Enum, 1);
  D.resize(Vnum);
  BW.resize(Vnum);
  lenall.resize(Enum, 1000000000);
  for (int(i) = 0; (i) < (Vnum); (i)++) {
    cin >> D[i].first;
    D[i].second = i;
  }
  sort(D.begin(), D.end(), less<pair<int, int> >());
  for (int(i) = 0; (i) < (Enum); (i)++) {
    if (graph_weight)
      cin >> edgelist[i].first >> edgelist[i].second >> edgeweight[i];
    else
      cin >> edgelist[i].first >> edgelist[i].second;
    if (graph_from1) {
      edgelist[i].first--;
      edgelist[i].second--;
    }
  }
  return;
}
void Graph_func::read_edge_array() {
  cin >> Vnum;
  Enum = 0;
  for (int(i) = 0; (i) < (Vnum); (i)++) {
    string S;
    cin >> S;
    for (int(j) = 0; (j) < (Vnum); (j)++) {
      if (S[j] == '1') {
        if (graph_digraph || i < j) {
          pair<int, int> edgetmp = make_pair(i, j);
          edgelist.push_back(edgetmp);
          Enum++;
        }
      }
    }
  }
  if (!graph_digraph) Enum /= 2;
  return;
}
void Graph_func::adjini() {
  adjnum.resize(Vnum);
  xdist.resize(Vnum);
  adjlist.resize(Vnum);
  if (graph_weight) adjlistweight.resize(Vnum);
  adj_to_root.resize(Vnum, -1);
  DP.resize(Vnum, 0);
  for (int(i) = 0; (i) < (Vnum); (i)++) adjnum[i] = 0;
  for (int(i) = 0; (i) < (Enum); (i)++) {
    int x = edgelist[i].first;
    int y = edgelist[i].second;
    adjlist[x].push_back(y);
    if (!graph_digraph) adjlist[y].push_back(x);
    if (graph_weight) {
      long long xyweight = edgeweight[i];
      adjlistweight[x].push_back(xyweight);
      if (!graph_digraph) adjlistweight[y].push_back(xyweight);
    }
    adjnum[x]++;
    if (!graph_digraph) adjnum[y]++;
  }
  x_visited.resize(Vnum);
  visited_ini();
  return;
}
void Graph_func::visited_ini() {
  for (int(i) = 0; (i) < (Vnum); (i)++) x_visited[i] = false;
  x_prqarr.resize(0);
}
void Graph_func::adjsort() {
  for (int(i) = 0; (i) < (Vnum); (i)++)
    sort(adjlist[i].begin(), adjlist[i].end(), less<int>());
  return;
}
vector<bool> Graph_func::graph_num_BFS(int BFS_ini, vector<bool> filled) {
  x_prqarr.push_back(BFS_ini);
  x_visited[BFS_ini] = true;
  while (!x_prqarr.empty()) {
    int Ntmp = x_prqarr.size();
    vector<int> x_prqarr_next(0);
    for (int(n) = 0; (n) < (Ntmp); (n)++) {
      int x = x_prqarr[n];
      for (int(i) = 0; (i) < (adjnum[x]); (i)++) {
        int x_new = adjlist[x][i];
        if (!x_visited[x_new]) {
          x_prqarr_next.push_back(x_new);
          x_visited[x_new] = true;
          filled[x_new] = true;
        }
      }
    }
    x_prqarr = x_prqarr_next;
  }
  return filled;
}
int Graph_func::graph_num() {
  int anstmp = 0;
  int i = 0;
  vector<bool> filled;
  filled.resize(Vnum);
  for (int(j) = 0; (j) < (Vnum); (j)++) filled[j] = false;
  bool end = false;
  while (!end) {
    if (i >= Vnum) break;
    while (1) {
      if (!filled[i]) break;
      i++;
      if (i >= Vnum) {
        end = true;
        break;
      }
    }
    if (end) break;
    filled[i] = true;
    filled = graph_num_BFS(i, filled);
    anstmp++;
  }
  return anstmp;
}
void Graph_func::graph_BFS(long long BFS_ini) {
  visited_ini();
  x_prqarr.push_back(BFS_ini);
  x_visited[BFS_ini] = true;
  vlist_from_root.resize(1, BFS_ini);
  while (!x_prqarr.empty()) {
    vector<int> x_prqarr_next(0);
    int Ntmp = x_prqarr.size();
    for (int(n) = 0; (n) < (Ntmp); (n)++) {
      int x = x_prqarr[n];
      for (int(i) = 0; (i) < (adjnum[x]); (i)++) {
        int x_new = adjlist[x][i];
        if (!x_visited[x_new]) {
          adj_to_root[x_new] = x;
          vlist_from_root.push_back(x_new);
          x_prqarr_next.push_back(x_new);
          x_visited[x_new] = true;
        }
      }
    }
    x_prqarr = x_prqarr_next;
  }
  return;
}
void Graph_func::graph_DFS(long long DFS_ini) {
  visited_ini();
  x_prqarr.push_back(DFS_ini);
  x_visited[DFS_ini] = true;
  while (!x_prqarr.empty()) {
    int Ntmp = x_prqarr.size();
    for (int(a) = 0; (a) < (Ntmp); (a)++) {
      int x = x_prqarr[x_prqarr.size() - 1];
      x_prqarr.pop_back();
      for (int(i) = 0; (i) < (adjnum[x]); (i)++) {
        int x_new = adjlist[x][i];
        if (!x_visited[x_new]) {
          adj_to_root[x_new] = x;
          x_prqarr.push_back(x_new);
          x_visited[x_new] = true;
        }
      }
    }
  }
  return;
}
void Graph_func::xydist_tree(int BFS_ini) {
  visited_ini();
  x_prqarr.push_back(BFS_ini);
  x_visited[BFS_ini] = true;
  xdist[BFS_ini] = 0;
  while (!x_prqarr.empty()) {
    vector<int> x_prqarr_next(0);
    int Ntmp = x_prqarr.size();
    for (int(n) = 0; (n) < (Ntmp); (n)++) {
      int x = x_prqarr[n];
      for (int(i) = 0; (i) < (adjnum[x]); (i)++) {
        int x_new = adjlist[x][i];
        int dist_new;
        if (graph_weight)
          dist_new = adjlistweight[x][i];
        else
          dist_new = 1;
        if (!x_visited[x_new]) {
          x_prqarr_next.push_back(x_new);
          xdist[x_new] = xdist[x] + dist_new;
          x_visited[x_new] = true;
        }
      }
    }
    x_prqarr = x_prqarr_next;
  }
  return;
}
void Graph_func::xydist(int x) {
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      xdist_que;
  long long max_tmp = pow(10, 18) * 4;
  for (int(i) = 0; (i) < (Vnum); (i)++) xdist[i] = max_tmp;
  xdist[x] = 0;
  pair<long long, int> xdist_que_tmp;
  xdist_que_tmp.first = 0;
  xdist_que_tmp.second = x;
  xdist_que.push(xdist_que_tmp);
  while (!xdist_que.empty()) {
    xdist_que_tmp = xdist_que.top();
    xdist_que.pop();
    long long xdist_tmp = xdist_que_tmp.first;
    int x_tmp = xdist_que_tmp.second;
    if (xdist[x_tmp] == xdist_tmp) {
      for (int(i) = 0; (i) < (adjnum[x_tmp]); (i)++) {
        int x_new = adjlist[x_tmp][i];
        long long dist_diff;
        if (graph_weight)
          dist_diff = adjlistweight[x_tmp][i];
        else
          dist_diff = 1;
        if (xdist[x_new] > xdist[x_tmp] + dist_diff) {
          xdist[x_new] = xdist[x_tmp] + dist_diff;
          xdist_que_tmp.first = xdist[x_new];
          xdist_que_tmp.second = x_new;
          xdist_que.push(xdist_que_tmp);
        }
      }
    }
  }
}
long long Graph_func::diameter() {
  long long anstmp = 0;
  if (graph_tree) {
    long long anstmp_i = 0;
    pair<int, int> longest;
    xydist_tree(0);
    for (int(i) = 0; (i) < (Vnum); (i)++) {
      if (xdist[i] > anstmp) {
        anstmp = xdist[i];
        anstmp_i = i;
      }
    }
    longest.first = anstmp_i;
    anstmp = 0, anstmp_i = 0;
    xydist_tree(longest.first);
    for (int(i) = 0; (i) < (Vnum); (i)++) {
      if (xdist[i] > anstmp) {
        anstmp = xdist[i];
        anstmp_i = i;
      }
    }
    longest.second = anstmp_i;
  } else {
    for (int(i) = 0; (i) < (Vnum); (i)++) {
      xydist(i);
      for (int(j) = 0; (j) < (Vnum); (j)++) {
        anstmp = max(anstmp, xdist[j]);
      }
    }
  }
  return anstmp;
}
void Graph_func::ReRooting(long long root) {
  for (int(i) = 0; (i) < (Vnum); (i)++) {
    DP[i] = 1;
  }
  graph_BFS(root);
  for (int i = Vnum - 1; i >= 0; i--) {
    long long x = vlist_from_root[i];
    for (int(j) = 0; (j) < (adjnum[x]); (j)++) {
      long long x_new = adjlist[x][j];
      if (x_new == adj_to_root[x]) continue;
      DP[x] += DP[x_new];
    }
  }
  return;
}
Graph_func Graph_func::Kruskal() {
  if (graph_digraph == true) {
    cout << "ERROR" << endl;
  }
  Graph_func tree;
  vector<pair<long long, pair<int, int> > > edgeweight_sort(Enum);
  for (int(i) = 0; (i) < (Enum); (i)++) {
    edgeweight_sort[i].first = edgeweight[i];
    edgeweight_sort[i].second = edgelist[i];
  }
  sort(edgeweight_sort.begin(), edgeweight_sort.end(),
       less<pair<long long, pair<int, int> > >());
  UnionFind tree_uf;
  tree_uf.UnionFind_ini(Vnum);
  tree.Vnum = Vnum;
  tree.Enum = 0;
  for (int(i) = 0; (i) < (Enum); (i)++) {
    long long edgeweighttmp = edgeweight_sort[i].first;
    pair<int, int> edgetmp = edgeweight_sort[i].second;
    if (!tree_uf.same(edgetmp.first, edgetmp.second)) {
      tree_uf.unite(edgetmp.first, edgetmp.second);
      tree.edgelist.push_back(edgetmp);
      tree.edgeweight.push_back(edgeweighttmp);
      tree.Enum++;
    }
  }
  long long ans = 0;
  for (int(i) = 0; (i) < (tree.Enum); (i)++) {
    ans += tree.edgeweight[i];
    cout << (tree.edgelist[i].first + 1) << " " << (tree.edgelist[i].second + 1)
         << " " << tree.edgeweight[i] << endl;
  }
  cout << ans << endl;
  tree.graph_from1 = true;
  tree.graph_tree = true;
  tree.graph_weight = true;
  tree.graph_digraph = false;
  tree.adjini();
  return tree;
}
int Graph_func::dim_num(int dim) {
  int anstmp = 0;
  for (int(i) = 0; (i) < (Vnum); (i)++) {
    if (adjnum[i] == dim) anstmp++;
  }
  return anstmp;
}
void Graph_func::solve() {
  if (D[0].first != D[1].first)
    cout << "-1" << endl;
  else {
    Graph_func graph_sub;
    for (int(i) = 0; (i) < (Vnum); (i)++) {
    }
  }
  return;
}
int main(void) {
  Graph_func graph;
  graph.read_edge();
  graph.adjini();
  graph.solve();
  return 0;
}
