using System;
using System.Collections.Generic;

class Edge
{
    public int Source { get; set; }
    public int Destination { get; set; }
    public int Weight { get; set; }

    public Edge(int source, int destination, int weight)
    {
        Source = source;
        Destination = destination;
        Weight = weight;
    }
}

class Graph
{
    private int _vertices;
    private List<Edge> _edges;

    public Graph(int vertices)
    {
        _vertices = vertices;
        _edges = new List<Edge>();
    }

    public void AddEdge(int source, int destination, int weight)
    {
        _edges.Add(new Edge(source, destination, weight));
    }

    public void BellmanFord(int start)
    {
        int[] distance = new int[_vertices];
        for (int i = 0; i < _vertices; i++)
        {
            distance[i] = int.MaxValue;
        }
        distance[start] = 0;

        for (int i = 1; i <= _vertices - 1; i++)
        {
            foreach (var edge in _edges)
            {
                int u = edge.Source;
                int v = edge.Destination;
                int weight = edge.Weight;
                if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
                {
                    distance[v] = distance[u] + weight;
                }
            }
        }

        // Check for negative-weight cycles
        foreach (var edge in _edges)
        {
            int u = edge.Source;
            int v = edge.Destination;
            int weight = edge.Weight;
            if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
            {
                Console.WriteLine("Graph contains negative weight cycle");
                return;
            }
        }

        Print(distance, start);
    }

    private void Print(int[] distance, int start)
    {
        Console.WriteLine("Vertex Distance from Source");
        for (int i = 0; i < _vertices; i++)
        {
            Console.WriteLine($"{i}\t\t{distance[i]}");
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph(5);
        graph.AddEdge(0, 1, -1);
        graph.AddEdge(0, 2, 4);
        graph.AddEdge(1, 2, 3);
        graph.AddEdge(1, 3, 2);
        graph.AddEdge(1, 4, 2);
        graph.AddEdge(3, 2, 5);
        graph.AddEdge(3, 1, 1);
        graph.AddEdge(4, 3, -3);

        graph.BellmanFord(0);
    }
}