package dataStructure;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

import java.io.*;

class node {

    int to, dist;

    node(int t, int d) {

        to = t;

        dist = d;

    }

}

public class Graph {

    public static void dfs(ArrayList<ArrayList<node> > map, int v, boolean[] vis) {

        vis[v] = true;

        System.out.print(v + "  ");

        ArrayList<node> rhs = map.get(v);

        for(int i=; i<rhs.size(); ++i) {

            int nv = rhs.get(i).to;

            if(!vis[nv])  dfs(map, nv, vis);

        }

    }

    public static void bfs(ArrayList<ArrayList<node> > map, int v) {

        boolean[] color = new boolean[map.size()];

        LinkedList<Integer> Q = new LinkedList<Integer> ();

        color[v] = true;

        Q.push(v);

        int d = ;

        System.out.print(v + "(" + d +")   ");

        while(!Q.isEmpty()) {

            int top = Q.peek();

            Q.pop();

            ++d;

            for(node nc: map.get(top)) {

                if(!color[nc.to]) {

                    color[nc.to] = true;

                    Q.push(nc.to);

                    System.out.print(nc.to + "(" + d +")   ");

                }

            }

        }

    }

    public static void caseInit(ArrayList<ArrayList<node> > map) {

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

        addEdge(map, , , );

    }

    public static void customize(ArrayList<ArrayList<node> > map) {

        Scanner input = new Scanner(System.in);

        while(true) {

            int v = input.nextInt();

            if(v == -)  break;

             int w = input.nextInt(), d = input.nextInt();

             addEdge(map, v, w, d);

        }

        input.close();

    }

    public static void addEdge(ArrayList<ArrayList<node> > map, int from, int to, int dist) {

        if(from <  || from >= map.size() || to <  || to >= map.size())  return;

        ArrayList<node> rhs = map.get(from);

        rhs.add(new node(to, dist));

        //ArrayList<node> rhs2 = map.get(to);

        //rhs2.add(new node(from, dist));

    }

    public static int[] dijkstra(ArrayList<ArrayList<node> > map, int v) {

        int[] min_dis = new int[map.size()];

        for(int i=; i<min_dis.length; ++i) min_dis[i] = Integer.MAX_VALUE;

        for(int i=; i<map.get(v).size(); ++i) {

            min_dis[map.get(v).get(i).to] = map.get(v).get(i).dist;

        }

        boolean[] vis = new boolean[map.size()];

        min_dis[v] = ;

        vis[v] = true;

        ArrayList<node> rhs = map.get(v);

        for(int i=; i<map.size(); ++i) {

            int Min = Integer.MAX_VALUE, Minj = v;

            for(int j=; j<map.size(); ++j) {

                if(!vis[j] && min_dis[j] < Min) {

                    Min = min_dis[j];

                    Minj = j;

                }

            }

            vis[Minj] = true;

            ArrayList<node> tmp = map.get(Minj);

            for(int k=; k<tmp.size(); ++k) {

                if(!vis[tmp.get(k).to] && min_dis[Minj] + tmp.get(k).dist < min_dis[tmp.get(k).to]) {

                    min_dis[tmp.get(k).to] = min_dis[Minj] + tmp.get(k).dist;

                }

            }

        }

        return min_dis;

    }

    public static void topologicalSort(ArrayList<ArrayList<node> > map) {

        int[] ind = new int[map.size()];

        for(int i=; i<map.size(); ++i) {

            for(node nc: map.get(i)) {

                ++ind[nc.to];

            }

        }

        LinkedList<Integer> Q = new LinkedList<Integer> ();

        for(int i=; i<map.size(); ++i) {

            if(ind[i] == ) {

                Q.addLast(i);

                //System.out.print(i + "  ");

            }

        }

        while(!Q.isEmpty()) {

            int top = Q.peek();

            System.out.print(top + "  ");

            Q.poll();

            for(node nc: map.get(top)) {

                --ind[nc.to];

                if(ind[nc.to] == ) Q.addLast(nc.to);

            }

        }

    }

    public static void main(String[] args) {

        ArrayList<ArrayList<node> > map = new ArrayList<ArrayList<node> > ();

        for(int i=; i<; ++i) {

            ArrayList<node> row = new ArrayList<node> ();

            map.add(row);

        }

        caseInit(map);

        int[] min_dis = dijkstra(map, );

        //for(int i=0; i<min_dis.length; ++i) System.out.print(min_dis[i] + "  ");

        //bfs(map, 0);

        topologicalSort(map);

    }

}