public void dijkstra(int s) {
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		q.add(new Edge(s, 0));
		dis[s] = 0;
		while (!q.isEmpty()) {
			Edge cur = q.poll();
			if (vis[cur.id])
				continue;
			vis[s] = true;
			for (int i = 0; i < adj[cur.id].size(); i++) {
				Edge neigh = adj[cur.id].get(i);
				if (!vis[neigh.id]) {
					if (dis[cur.id] + neigh.w < dis[neigh.id]) {
						dis[neigh.id] = dis[cur.id] + neigh.w;
						parent[neigh.id] = cur.id;
						q.add(new Edge(neigh.id, dis[neigh.id]));
					}
				}
			}
		}
	}