import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.Queue; public class Main { public static int[][] cost; public static int n; public static int inf; public static boolean[][] check; public static boolean[] checked; public static int[][] start; public static void main(String[] args) throws NumberFormatException, IOException{ ContestScanner in = new ContestScanner("input.dat"); n = in.nextInt(); int m = in.nextInt(); int s = in.nextInt(); int g = in.nextInt(); // Node[] node = new Node[n]; inf = 100000000; check = new boolean[n][n]; cost = new int[n][n]; start = new int[n][n]; checked = new boolean[n]; // for(int i=0; i qu = new PriorityQueue(); // node[s].sum = 0; // checked[s] = true; // qu.add(node[s]); // while(!qu.isEmpty()){ // Node nd = qu.poll(); // // } for(int l=0; l<4; l++) for(int i=0; i cost[i][k]+cost[k][j]){ cost[i][j] = cost[i][k]+cost[k][j]; } } } } // for(int i=0; i start[now][i]+cost[i][g]){ minid = i; min = start[now][i]+cost[i][g]; } } System.out.print(minid+" "); now = minid; checked[now] = true; } System.out.println(); // for(int i=0; i start[now][i]+cost[i][g]){ minid = i; min = start[now][i]+cost[i][g]; } } System.out.print(minid+" "); dfs(s, minid, g); } } class MyComp implements Comparator{ public int compare(int[] a, int[] b) { return a[0] - b[0]; } } class Reverse implements Comparator{ public int compare(Integer arg0, Integer arg1) { return arg1 - arg0; } } class Node implements Comparable{ int id; List edge = new ArrayList(); // List cost = new ArrayList(); int sum; public Node(int id){ this.id = id; sum = 100000000; } public void createEdge(Node node){ edge.add(node); // cost.add(c); } @Override public int compareTo(Node o) { // TODO 自動生成されたメソッド・スタブ return sum - o.sum; } } class ContestWriter{ private PrintWriter out; public ContestWriter(String filename) throws IOException{ out = new PrintWriter(new BufferedWriter(new FileWriter(filename))); } public ContestWriter() throws IOException{ out = new PrintWriter(System.out); } public void println(String str){ out.println(str); } public void print(String str){ out.print(str); } public void close(){ out.close(); } } class ContestScanner{ private BufferedReader reader; private String[] line; private int idx; public ContestScanner() throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(System.in)); } public ContestScanner(String filename) throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); } public String nextToken() throws IOException{ if(line == null || line.length <= idx){ line = reader.readLine().trim().split(" "); idx = 0; } return line[idx++]; } public long nextLong() throws IOException, NumberFormatException{ return Long.parseLong(nextToken()); } public int nextInt() throws NumberFormatException, IOException{ return (int)nextLong(); } public double nextDouble() throws NumberFormatException, IOException{ return Double.parseDouble(nextToken()); } }