struct Edge {
  int source, dest, weight;
};
void printPath(vector<int> const &parent, int vertex, int source) {
  if (vertex < 0) {
    return;
  }
  printPath(parent, parent[vertex], source);
  if (vertex != source) {
    cout << ", ";
  }
  cout << vertex;
}
void bellmanFord(vector<Edge> const &edges, int source, int n) {
  vector<int> distance(n, INT_MAX);
  distance[source] = 0;
  vector<int> parent(n, -1);
  int u, v, w, k = n;
  while (--k) {
    for (Edge edge : edges) {
      u = edge.source;
      v = edge.dest;
      w = edge.weight;
      if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
        distance[v] = distance[u] + w;
        parent[v] = u;
      }
    }
  }
  for (Edge edge : edges) {
    u = edge.source;
    v = edge.dest;
    w = edge.weight;
    if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
      cout << "Negative-weight cycle is found!!";
      return;
    }
  }
  for (int i = 0; i < n; i++) {
    if (i != source && distance[i] < INT_MAX) {
      cout << "The distance of vertex " << i << " from the source is "
           << setw(2) << distance[i] << ". Its path is [";
      printPath(parent, i, source);
      cout << "]" << endl;
    }
  }
}