Kenkoooo is planning a trip in Republic of Snuke. In this country, there are n cities and m trains running. The cities are numbered 1 through n, and the i-th train connects City u_i and v_i bidirectionally. Any city can be reached from any city by changing trains.

Two currencies are used in the country: yen and snuuk. Any train fare can be paid by both yen and snuuk. The fare of the i-th train is a_i yen if paid in yen, and b_i snuuk if paid in snuuk.

In a city with a money exchange office, you can change 1 yen into 1 snuuk. However, when you do a money exchange, you have to change all your yen into snuuk. That is, if Kenkoooo does a money exchange when he has X yen, he will then have X snuuk. Currently, there is a money exchange office in every city, but the office in City i will shut down in i years and can never be used in and after that year.

Kenkoooo is planning to depart City s with 10^{15} yen in his pocket and head for City t, and change his yen into snuuk in some city while traveling. It is acceptable to do the exchange in City s or City t.

Kenkoooo would like to have as much snuuk as possible when he reaches City t by making the optimal choices for the route to travel and the city to do the exchange. For each i=0,...,n-1, find the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i years. You can assume that the trip finishes within the year.

Constraints

* 2 \leq n \leq 10^5
* 1 \leq m \leq 10^5
* 1 \leq s,t \leq n
* s \neq t
* 1 \leq u_i < v_i \leq n
* 1 \leq a_i,b_i \leq 10^9
* If i\neq j, then u_i \neq u_j  or v_i \neq v_j.
* Any city can be reached from any city by changing trains.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


n m s t
u_1 v_1 a_1 b_1
:
u_m v_m a_m b_m


Output

Print n lines. In the i-th line, print the maximum amount of snuuk that Kenkoooo has when he reaches City t if he goes on a trip from City s to City t after i-1 years.

Examples

Input

4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1


Output

999999999999998
999999999999989
999999999999979
999999999999897


Input

8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879


Output

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt()-1;
        int t = in.nextInt()-1;
        ArrayList<ArrayList<int[]>> edge_yen = new ArrayList<ArrayList<int[]>>();
        ArrayList<ArrayList<int[]>> edge_snuke = new ArrayList<ArrayList<int[]>>();
        for (int i=0;i<n;i++) {
            ArrayList<int[]> add_yen = new ArrayList<int[]>();
            ArrayList<int[]> add_snuke = new ArrayList<int[]>();
            edge_yen.add(add_yen);
            edge_snuke.add(add_snuke);
        }
        for (int i=0;i<m;i++) {
            int u = in.nextInt()-1;
            int v = in.nextInt()-1;
            int a = in.nextInt();
            int b = in.nextInt();
            int[] add_yen_1 = {v, a};
            int[] add_yen_2 = {u, a};
            int[] add_snuke_1 = {v, b};
            int[] add_snuke_2 = {u, b};
            edge_yen.get(u).add(add_yen_1);
            edge_yen.get(v).add(add_yen_2);
            edge_snuke.get(u).add(add_snuke_1);
            edge_snuke.get(v).add(add_snuke_2);
        }

        long[] dijkstra_yen = new long[n];
        Arrays.fill(dijkstra_yen, -1);
        PriorityQueue<long[]> pq_yen = new PriorityQueue<long[]>((o1, o2)->Long.compare(o1[1], o2[1]));
        long[] first_yen = {s, 0};
        pq_yen.add(first_yen);
        while (!pq_yen.isEmpty()) {
            long[] tmp = pq_yen.poll();
            if (dijkstra_yen[(int)tmp[0]]!=-1) continue;
            dijkstra_yen[(int)tmp[0]] = tmp[1];
            for (int[] arr : edge_yen.get((int)tmp[0])) {
                long[] add_arr = {arr[0], arr[1]+tmp[1]};
                pq_yen.add(add_arr);
            }
        }

        long[] dijkstra_snuke = new long[n];
        Arrays.fill(dijkstra_snuke, -1);
        PriorityQueue<long[]> pq_snuke = new PriorityQueue<long[]>((o1, o2)->Long.compare(o1[1], o2[1]));
        long[] first_snuke = {t, 0};
        pq_snuke.add(first_snuke);
        while (!pq_snuke.isEmpty()) {
            long[] tmp = pq_snuke.poll();
            if (dijkstra_snuke[(int)tmp[0]]!=-1) continue;
            dijkstra_snuke[(int)tmp[0]] = tmp[1];
            for (int[] arr : edge_snuke.get((int)tmp[0])) {
                long[] add_arr = {arr[0], arr[1]+tmp[1]};
                pq_snuke.add(add_arr);
            }
        }

        long[] cost = new long[n];
        TreeMap<Long, Long> map = new TreeMap<Long, Long>();
        for (int i=0;i<n;i++) {
            cost[i] = dijkstra_yen[i]+dijkstra_snuke[i];
            if (map.containsKey(cost[i])) {
                map.put(cost[i], map.get(cost[i])+1);
            } else {
                map.put(cost[i], 1L);
            }
        }
        for (int i=0;i<n;i++) {
            out.println(1_000_000_000_000_000L-map.firstKey());
            if (map.get(cost[i])>1) {
                map.put(cost[i], map.get(cost[i])-1);
            } else {
                map.remove(cost[i]);
            }
        }
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}
