You are given a tree (a connected undirected graph without cycles) of n vertices. Each of the n - 1 edges of the tree is colored in either black or red.

You are also given an integer k. Consider sequences of k vertices. Let's call a sequence [a_1, a_2, …, a_k] good if it satisfies the following criterion:

  * We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from a_1 and ending at a_k. 
  * Start at a_1, then go to a_2 using the shortest path between a_1 and a_2, then go to a_3 in a similar way, and so on, until you travel the shortest path between a_{k-1} and a_k.
  * If you walked over at least one black edge during this process, then the sequence is good. 

<image>

Consider the tree on the picture. If k=3 then the following sequences are good: [1, 4, 7], [5, 5, 3] and [2, 3, 7]. The following sequences are not good: [1, 4, 6], [5, 5, 5], [3, 7, 3].

There are n^k sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo 10^9+7.

Input

The first line contains two integers n and k (2 ≤ n ≤ 10^5, 2 ≤ k ≤ 100), the size of the tree and the length of the vertex sequence.

Each of the next n - 1 lines contains three integers u_i, v_i and x_i (1 ≤ u_i, v_i ≤ n, x_i ∈ \{0, 1\}), where u_i and v_i denote the endpoints of the corresponding edge and x_i is the color of this edge (0 denotes red edge and 1 denotes black edge).

Output

Print the number of good sequences modulo 10^9 + 7.

Examples

Input


4 4
1 2 1
2 3 1
3 4 1


Output


252

Input


4 6
1 2 0
1 3 0
1 4 0


Output


0

Input


3 5
1 2 1
2 3 0


Output


210

Note

In the first example, all sequences (4^4) of length 4 except the following are good: 

  * [1, 1, 1, 1]
  * [2, 2, 2, 2]
  * [3, 3, 3, 3]
  * [4, 4, 4, 4] 



In the second example, all edges are red, hence there aren't any good sequences.
import java.util.*; 
import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.util.StringTokenizer; 
import java.io.IOException; 
import java.math.*;


public class cp{

    static long pow(long x, long y, long p){ 
        // Initialize result 
        long res = 1;      
         
        // Update x if it is more   
        // than or equal to p 
        x = x % p;  
      
        while (y > 0) 
        { 
            // If y is odd, multiply x 
            // with result 
            if((y & 1)==1) 
                res = (res * x) % p; 
      
            // y must be even now 
            // y = y / 2 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    } 
  

	public static void main(String[] args) throws IOException{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer s = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(s.nextToken());

		int k = Integer.parseInt(s.nextToken());

		int m = n - 1;
		int[][] edges = new int[m][3];
		for(int i = 0; i < m; i ++){
			s = new StringTokenizer(br.readLine());
			edges[i][0] = Integer.parseInt(s.nextToken()) - 1;
			edges[i][1] = Integer.parseInt(s.nextToken()) - 1;
			edges[i][2] = Integer.parseInt(s.nextToken());
		}

		Graph graph = new Graph(n, m, false, edges, true, false);

		// graph.displayAdjacencyList();

		//graph.displayConnectedComponents();

		// Linklist topologicalSort = graph.topologicalSort();

		Linklist components = graph.getCountConnectedComponents();

		components.print();
		Node ptr = components.front;

		long ans = pow(n, k, 1000000007);
		// System.out.println(ans + " " + n + k);
		while(ptr != null){

			ans = (ans - pow(ptr.data, k, 1000000007));
			if( ans < 0){
				ans = 1000000007 - ans;
			}
			// System.out.println(ans);
			ptr = ptr.next;
		}

		System.out.println(ans);
	}
}


class Node{
	public int data;
	public Node next;

	public Node(int data){
		this.data = data;
		this.next = null;
	}

	public int getData(){
		return data;
	}

	public Node getNextNode(){
		return next;
	}

	public void setData(int data){
		this.data = data;
	}

	public void setNextNode(Node next){
		this.next = next;
	}
}

class Linklist{
	public Node front;

	public Node getFront(){
		return front;
	}

	public void print(){
		Node ptr = front;

		while(ptr!=null){
			System.out.print(ptr.getData()+" ");
			ptr = ptr.getNextNode();
		}
		System.out.println("");
	}

	public int length(){
		int count = 0;
		Node curr = front;
		while(curr!= null){
			count++;
			curr = curr.getNextNode();
		}
		return count;
	}

	public void addNode(int data, int position){
		Node nptr = new Node(data);
		if(front == null){
			front = nptr;
		}
		if(position == 1){
			nptr.setNextNode(front.getNextNode());
			front = nptr;
		}else{
			Node prev = front;
			Node curr = front.getNextNode();
			while(position -- > 2){
				curr = curr.getNextNode();
				prev = prev.getNextNode();
			}
			nptr.setNextNode(curr);
			prev.setNextNode(nptr);
		}
	}

	public void addNode(int data){
		addNode(data,length()+1);
	}

	public void deleteNode(int position){
		if(position == 1){
			front = front.getNextNode();
		}else{
			Node prev = front;
			Node curr = front.getNextNode();

			while(position -- > 2){
				curr = curr.getNextNode();
				prev = prev.getNextNode();
			}

			prev.setNextNode(curr.getNextNode());
		}
	}

	public void recDelete(int position, Node ptr){
		if(position == 1){
			front = front.getNextNode();
		}else if(position == 2){
			ptr.setNextNode(ptr.getNextNode().getNextNode());
		}else{
			ptr = ptr.getNextNode();
			recDelete(position - 1, ptr);
		}
	}

	public void reverse(){
		Node prev = front;
		Node curr = prev.getNextNode();
		Node next = curr;
		while(curr!=null){
			next = next.getNextNode();
			curr.setNextNode(prev);
			prev = curr;
			curr = next;
		}
		front.setNextNode(null);
		front = prev;
	}

	public int makeAlt(Node curr, boolean state, Node mid){
		if(curr == null){
			return mid.getData();
		}
		if(state){
			mid = mid.getNextNode();
		}

		return makeAlt(curr.getNextNode(),!state, mid);
	}
}

class Stack{
	private Node top;
	private int size;

	public Stack(){
		size = 0;
	}

	public void push( int data){
		Node node = new Node(data);
		node.setNextNode(top);
		top = node;

		size++;
	}

	public int pop(){
		int ret = top.getData();
		top = top.getNextNode();
		size--;
		return ret;
	}

	public int peek(){
		return top.getData();
	}

	public int size(){
		return size;
	}

	public boolean isEmpty(){
		return size == 0;
	}
}

class Queue{
	Node front;
	Node rear;
	int size;

	public Queue(){
		size = 0;
	}

	public void enqueue(int data){
		size += 1;
		if(front == null){
			front = new Node(data);
			rear = front;
			return;
		}
		Node nptr = new Node(data);
		nptr.setNextNode(front.getNextNode());
		front.setNextNode(nptr);
		front = nptr; 
	}

	public int dequeue(){
		if(rear == null){
			System.out.println("error: Queue empty");
			return -1;
		}
		size -= 1;
		int curr = rear.getData();
		rear = rear.getNextNode();
		if(rear == null){
			front = null;
		}
		return curr;
	}

	public void print(){
		Node ptr = rear;
		while(ptr!= null){
			System.out.print(ptr.getData()+" ");
			ptr = ptr.getNextNode();
		}
		System.out.println("");
	}

	public boolean isEmpty(){
		return size == 0;
	}
}

class BinarySearchTree{

	int data;
	BinarySearchTree left;
	BinarySearchTree right;

	public BinarySearchTree(){
	}

	public BinarySearchTree(int data){
		this.data = data;
	}

	public void insertInt( int data ){
		BinarySearchTree tree = new BinarySearchTree( data );

		insert( tree );
	}

	public void insert(BinarySearchTree tree){
		if(tree.data < this.data){
			if(this.left == null){
				this.left = tree;
			}else{
				this.left.insert( tree );
			}
		}else{
			if(this.right == null){
				this.right = tree;
			}else{
				this.right.insert( tree );
			}
		}
	}

	public void delete(int data){
		if(contains(data)){
			delete(data, null, true);
		}else{
			System.out.println("Not found!");
		}
	}

	public void delete(int data, BinarySearchTree parent, boolean isLeftChild){
		if(data == this.data){
			if(this.left == null && this.right == null){
				if(parent == null){
					System.out.println("Can't delete only node of tree!");
					return;
				}
				if(isLeftChild){
					parent.left = null;
				}else{
					parent.right = null;
				}
			}else if(this.left != null && this.right != null){
				int minValue = this.right.getMin();
				delete(minValue, null, true);
				this.data = minValue;
			}else if(this.right != null){
				this.left = this.right.left;
				this.data = this.right.data;
				this.right = this.right.right;
			}else{
				this.right = this.left.right;
				this.data = this.left.data;
				this.left = this.left.left;
			}
		}else if(data < this.data){
			this.left.delete(data, this, true);

		}else if(data > this.data){
			this.right.delete(data, this, false);
		}
	}

	public BinarySearchTree getParent(int data){
		if(this.data == data){
			return null;
		}else if(data < this.data){
			if(data == this.left.data){
				return this;
			}else{
				return this.left.getParent(data);
			}
		}else{
			if(data == this.right.data){
				return this;
			}else{
				return this.right.getParent(data);
			}
		}
	}

	public boolean contains( int data ){
		if( data == this.data){
			return true;
		}
		else if( data < this.data){
			if( this.left == null ){
				return false;
			}
			return this.left.contains( data );
		}
		else if( data > this.data){
			if( this.right == null ){
				return false;
			}
			return this.right.contains( data );
		}

		return false;
	}

	public int getMax(){
		if(this.right == null){
			return this.data;
		}
		return this.right.getMax();
	}

	public int getMin(){
		if(this.left == null){
			return this.data;
		}else{
			return this.left.getMin();
		}
	}

	public void display(){
		displayWithIndent(0);
	}

	private void displayWithIndent(int indent){
		for(int i = 0;i < indent; i++){
			System.out.print(" ");
		}System.out.println(this.data);
		
		if(this.left != null){
			for(int i = 0;i < indent; i++){
				System.out.print(" ");
			}System.out.println("left: ");
			this.left.displayWithIndent(indent + 2);			
		}

		if(this.right != null){
			for(int i = 0;i < indent + 2; i++){
				System.out.print(" ");
			}System.out.println("right: ");
			this.right.displayWithIndent(indent + 2);			
		}
	}
	public void printSorted(){
		if(this.left != null){
			left.printSorted();
		}
		System.out.println(this.data);
		if(this.right != null){
			right.printSorted();
		}
	}
}

class AVLTree{

    int data;
    int height;
    AVLTree left;
    AVLTree right;

    private static int ALLOWED_IMBALANCE = 1;

    AVLTree(){
        this.data = -1;
        height = 0;
    }

    AVLTree(int data){
        this.data = data;
        height = 0;
    }

    public void insert(int data){
        if(this.data == -1){
            this.data = data;
            return;
        }
        if(data < this.data){
            if(this.left == null){
                this.left = new AVLTree(data);
            }else{
                this.left.insert(data);
            }
        }else{
            if(this.right == null){
                this.right = new AVLTree(data);
            }else{
                this.right.insert(data);
            }
        }

        balance();
    }

    public void delete(int data){
        if(data == this.data){
            if(this.left == null && this.right == null){
                System.out.println("Can't delete only node of tree");
                return;
            }else if(this.left != null && this.right != null){
                int leftmostOfRightChild = this.right.findMin();
                delete(leftmostOfRightChild);
                this.data = leftmostOfRightChild;
            }else if(this.left != null && this.right == null){
                this.data = this.left.data;
                this.right = this.left.right;
                this.left = this.left.left;
            }else if(this.left == null && this.right != null){
                this.data = this.right.data;
                this.left = this.right.left;
                this.right = this.right.right;
            }
        }else if(data < this.data){
            if(this.left == null){
                System.out.println( data + " not Found" );
                return;
            }else{
                if(data == this.left.data && this.left.left == null && this.left.right == null){
                    this.left = null;
                }else{
                    this.left.delete(data);
                }
            }
        }else{
            if(this.right == null){
                System.out.println( data + " not Found" );
                return;
            }else{
                if(data == this.right.data && this.right.right == null && this.right.left == null){
                    this.right = null;
                }else{
                    this.right.delete(data);
                }
            }            
        }
        balance();
    }

    public int findMin(){
        if(this.left == null){
            return this.data;
        }else{
            return this.left.findMin();
        }
    }

    private void balance(){
        if(this.left != null){
            this.left.balance();
        }
        if(this.right != null){
            this.right.balance();
        }
        int leftHeight = this.left == null ? 0 : this.left.height;
        int rightHeight = this.right == null ? 0 : this.right.height;
        System.out.println(this.data + " leftHeight: " + leftHeight + " rightHeight: " + rightHeight);
        if(leftHeight - rightHeight > ALLOWED_IMBALANCE){
            if(this.left.left != null && this.left.left.height - (rightHeight - 1) > 1){
                singleRotationRight();
            }else if(this.left.right != null && this.left.right.height - (rightHeight - 1) > 1){
                doubleRotationRight();
            }
        }else if(leftHeight - rightHeight < -1*ALLOWED_IMBALANCE){
            if(this.right.right != null && this.right.right.height - (leftHeight - 1) > 1){
                singleRotationLeft();
            }else if(this.right.left != null && this.right.left.height - (leftHeight - 1) > 1){
                doubleRotationLeft();
            }
        }

        if(this.left == null && this.right == null){
            this.height = 1;
        }else if(this.left == null && this.right != null){
            this.height = 1 + this.right.height;
        }else if(this.left != null && this.right == null){
            this.height = 1 + this.left.height;
        }else{
            this.height = 1 + this.left.height > this.right.height ? this.left.height : this.right.height;
        }
    }

    private void singleRotationLeft(){
        int k1 = this.data;
        int k2 = this.right.data;

        AVLTree x = this.right.right;
        AVLTree y = this.right.left;
        AVLTree z = this.left;

        this.data = k2;
        this.left = this.right;
        this.right.right = y;
        this.right.right = z;
        this.right = x;
        this.left.data = k1; 
    }

    private void singleRotationRight(){
        int k1 = this.data;
        int k2 = this.left.data;

        AVLTree x = this.left.left;
        AVLTree y = this.left.right;
        AVLTree z = this.right;

        this.data = k2;
        this.right = this.left;
        this.right.left = y;
        this.right.right = z;
        this.left = x;
        this.right.data = k1;

    }

    private void doubleRotationLeft(){
        this.right.singleRotationRight();
        singleRotationLeft();
    }

    private void doubleRotationRight(){
        this.left.singleRotationLeft();
        singleRotationRight();
    }

    public void display(){
        displayWithIndent(0);
    }

    private void displayWithIndent(int indent){
        for(int i = 0; i < indent; i ++){
            System.out.print(" ");
        }System.out.println(this.data);

        for(int i = 0; i < indent + 2; i ++){
            System.out.print(" ");
        }System.out.println("left: ");
        if(this.left != null){
            this.left.displayWithIndent(indent + 2);
        }
        for(int i = 0; i < indent + 2; i ++){
            System.out.print(" ");
        }System.out.println("right: ");
        if(this.right != null){
            this.right.displayWithIndent(indent + 2);
        }
    }
}

class Heap{
    int[] heap;
    int size;
    boolean parentShouldHaveLowerValue;

    Heap(int size){
        heap = new int[size];
        this.size = 0;
        this.parentShouldHaveLowerValue = true;
    }

    Heap(){}

    public void heapify(int [] arr, boolean parentShouldHaveLowerValue){
        this.heap = arr;
        this.parentShouldHaveLowerValue = parentShouldHaveLowerValue;
        this.size = arr.length;
        for(int i = size - 1; i >= 0; i --){
            percolateDown(i);
        }
    }

    public void insert(int data){
        heap[size++] = data;
        percolateUp(size - 1);
    }

    public int popHighestPriority(){
        int highestPriority = heap[0];

        heap[0] = heap[size - 1];
        size --;
        percolateDown(0);

        return highestPriority;
    }

    public void percolateUp(int curr){
        int parent = curr%2 == 0 ? curr/2 - 1 : curr/2;
        if(parent < 0){
            return;
        }
        if(isHigherPriority(curr, parent)){
            int temp = heap[parent];
            heap[parent] = heap[curr];
            heap[curr] = temp;
            percolateUp(parent);
        } 
    }

    public void percolateDown(int curr){
        int leftChild = 2*curr + 1;
        int rightChild = 2*curr + 2;
        
        int switchWith = -1;
        if(leftChild < size){
            if(!isHigherPriority(curr, leftChild)){
                switchWith = leftChild;
            }
        }
        if(rightChild < size){
            if(!isHigherPriority(curr, rightChild)){
                if(switchWith == -1 || isHigherPriority(rightChild, leftChild)){
                    switchWith = rightChild;
                }
            }
        }

        if(switchWith != -1){
            int temp = heap[switchWith];
            heap[switchWith] = heap[curr];
            heap[curr] = temp;
            percolateDown(switchWith);
        }
    }

    public static int[] heapSort(int arr[], boolean ascending){
        Heap heap = new Heap();
        int n = arr.length;
        heap.heapify(arr, !ascending);
        for(int i = 0; i < n; i++){
            heap.heap[n - i - 1] = heap.popHighestPriority();
        }
        return heap.heap;
    }

    public boolean isHeap(){
        for(int curr = 0; curr < size; curr ++){
            int leftChild = 2*curr + 1;
            int rightChild = 2*curr + 2;

            if(leftChild < size && !isHigherPriority(curr, leftChild)){
                return false;
            }
            if(rightChild < size && !isHigherPriority(curr, rightChild)){
                return false;
            }
        }
        return true;
    }

    public void displaySimple(){
        System.out.println("Heap: ");
        int j = 2;
        for(int i = 0; i < size; i ++){
            System.out.print(heap[i] + " ");

            if(i == j - 2){
                System.out.println("");
                j *= 2;
            }
        }System.out.println("");
        System.out.println("Is this a heap? " + (isHeap() ? "yes" : "no"));
    }

    public boolean isHigherPriority(int parent, int child){
        if(this.parentShouldHaveLowerValue){
            if(heap[parent] > heap[child]){
                return false;
            }else{
                return true;
            }
        }else{
            if(heap[parent] < heap[child]){
                return false;
            }else{
                return true;
            }
        }
    }
}

class Graph{
	public int n;
	public int m;
	public boolean isDirected;
	public int[][] edges;
	public boolean[][] adjacencyMatrix;
	public Linklist[] adjacencyList;

	Graph(int n, int m, boolean isDirected, int[][] edges, boolean createList, boolean createMatrix ){
		this.n = n;
		this.m = m;
		this.isDirected = isDirected;
		this.edges = edges;
		if(createList){
			createAdjacencyList();
		}
		if(createMatrix){
			createAdjacencyMatrix();
		}
	}

	public void createAdjacencyMatrix(){
		adjacencyMatrix = new boolean[n][n];
		for(int i = 0; i < m; i ++){
			adjacencyMatrix[edges[i][0]][edges[i][1]] = true;
			if(!isDirected){
				adjacencyMatrix[edges[i][1]][edges[i][0]] = true;
			}
		}
	}

	public void displayAdjacencyMatrix(){
		for(int i = 0; i < n; i ++){
			for(int j = 0; j < n; j ++){
				System.out.print(adjacencyMatrix[i][j] + " ");
			}System.out.println("");
		}
	}

	public void createAdjacencyList(){
		adjacencyList = new Linklist[n];
		for(int i = 0; i < n; i ++){
			adjacencyList[i] = new Linklist();
		}
		for(int i = 0; i < m; i ++){
			if(edges[i][2] == 1){
				continue;
			}
			adjacencyList[edges[i][0]].addNode(edges[i][1]);
			if(!isDirected){
				adjacencyList[edges[i][1]].addNode(edges[i][0]);
			}
		}
	}

	public void displayAdjacencyList(){
		for(int i = 0; i < n; i ++){
			System.out.print(i + ": ");
			adjacencyList[i].print();
		}
	}	

	//returns the sink node or -1 if no sink exists
	public int getSink(){
		if(n == 1){
			return -1;
		}
		int row = 0;
		int column = 0;

		while(column < n){
			if(adjacencyMatrix[row][column] == true){
				row = column;
				column += 1;
			}else{
				column += 1;
			}
		}
		int potentialNode = row;
		for(int i = 0; i < n; i++){
			if(i == potentialNode || (adjacencyMatrix[potentialNode][i] == false && adjacencyMatrix[i][potentialNode] == true)){
				continue;
			}
			return -1;
		}

		return potentialNode;
	}

	//if x is connected to y then returns true
	public boolean areConnected(int x, int y){
		Stack stack = new Stack();
		boolean[] visited = new boolean[n];
		visited[x] = true;
		stack.push(x);
		while(!stack.isEmpty()){
			int curr = stack.pop();
			Linklist neighbours = adjacencyList[curr];

			Node ptr = neighbours.front;

			while(ptr != null){
				if(visited[ptr.data]){
					ptr = ptr.next;
					continue;
				}
				if(ptr.data == y){
					return true;
				}
				visited[ptr.data] = true;
				stack.push(ptr.data);

				ptr = ptr.next;
			}
		}
		return false;
	}

	//Displaying all connected components using dfs:
	public Linklist getCountConnectedComponents(){
		boolean[] visited = new boolean[n];
		Linklist connected = new Linklist();

		for(int i = 0; i < n; i ++){
			if(visited[i]){
				continue;
			}
			int count = 0;
			Stack stack = new Stack();
			visited[i] = true;
			stack.push(i);
			while(!stack.isEmpty()){
				int curr = stack.pop();
				count += 1;

				Linklist neighbours = adjacencyList[curr];
				Node ptr = neighbours.front;

				while (ptr != null) {
					if(visited[ptr.data]){
						ptr = ptr.next;
						continue;
					}
					visited[ptr.data] = true;
					stack.push(ptr.data);
					ptr = ptr.next;
				}
			}
			connected.addNode(count);
		}

		return connected;
	}

	//Works for both directed and undirected :p
	public boolean cyclePresent(){
		return isDirected ? cyclePresentDirected() : cyclePresentUndirected();
	}

	//Works only for undirected graphs
	//for directed 1 2, 1 3, 2 3, 3 will be visited when we come from 2 to 3 hence gives true even though no cycle present
	public boolean cyclePresentUndirected(){
		boolean[] visited = new boolean[n];

		Stack stack = new Stack();
		for(int i = 0; i < n; i ++){
			if(visited[i]){
				continue;
			}
			visited[i] = true;
			stack.push(i);
			while(!stack.isEmpty()){
				int curr = stack.pop();
				Node ptr = adjacencyList[curr].front;

				int count = 0;
				while(ptr != null){
					// System.out.println(curr + " " + ptr.data);
					if(visited[ptr.data]){
						count += 1;
						ptr = ptr.next;
						continue;
					}
					visited[ptr.data] = true;
					stack.push(ptr.data);
					ptr = ptr.next;
				}

				if(count > 1){
					// System.out.println(curr);
					return true;
				}
			}			
		}


		return false;
	}

	//Works only for directed graphs as topologicalSort() is not defined for undirected
	public boolean cyclePresentDirected(){
		return topologicalSort() == null;
	}

	//Returns linklist with topological sorting of the Directed acyclic graph. If the directed graph is cyclic it returns null
	public Linklist topologicalSort(){
		Queue queue = new Queue();
		Linklist topologicalSort = new Linklist();
		int[] inDegree = new int[n];

		boolean[] visited = new boolean[n];

		for(int i = 0; i < n; i ++){
			Node ptr = adjacencyList[i].front;
			while(ptr != null){
				inDegree[ptr.data] += 1;
				ptr = ptr.next;
			}
		}

		for(int i = 0; i < n; i ++){
			if(inDegree[i] == 0){
				queue.enqueue(i);
				visited[i] = true;
			}
		}
		while(!queue.isEmpty()){
			int curr = queue.dequeue();

			topologicalSort.addNode(curr);
			Node ptr = adjacencyList[curr].front;

			while(ptr != null){
				if(visited[ptr.data]){
					ptr = ptr.next;
					continue;
				}
				inDegree[ptr.data] -= 1;

				if(inDegree[ptr.data] == 0){
					visited[ptr.data] = true;
					queue.enqueue(ptr.data);
				}
				ptr = ptr.next;
			}
		}

		if(topologicalSort.length() == n){
			return topologicalSort;
		}else{
			return null;
		}
	}

	public int[] distanceToAllPoints(int x){
		Queue queue = new Queue();

		int[] distance = new int[n];

		for(int i = 0; i < n; i ++){
			distance[i] = Integer.MAX_VALUE;
		}

		distance[x] = 0;
		queue.enqueue(x);

		while(!queue.isEmpty()){
			int curr = queue.dequeue();
			
			Node ptr = adjacencyList[curr].front;

			while(ptr != null){
				if(distance[ptr.data] != Integer.MAX_VALUE){

					ptr = ptr.next;
					continue;
				}
				queue.enqueue(ptr.data);
				distance[ptr.data] = distance[curr] + 1;
				ptr = ptr.next;
			}
		}
		return distance;
	}

	public Linklist getShortestPath(int x, int y){
		Queue queue = new Queue();
		int[] parent = new int[n];
		boolean[] visited = new boolean[n];
		parent[x] = -1;

		queue.enqueue(x);
		visited[x] = true;
		while(!queue.isEmpty()){
			int curr = queue.dequeue();

			Node ptr = adjacencyList[curr].front;

			while(ptr != null){
				if(visited[ptr.data]){
					ptr = ptr.next;
					continue;
				}

				visited[ptr.data] = true;
				parent[ptr.data] = curr;

				if(ptr.data == y){
					break;
				}
				queue.enqueue(ptr.data);
			}
		}

		Linklist path = new Linklist();
		int i = y;
		path.addNode(i + 1);
		while(i != x){
			i = parent[i];
			path.addNode(i + 1);
		}
		return path;
	}
}


