Codefortia is a small island country located somewhere in the West Pacific. It consists of n settlements connected by m bidirectional gravel roads. Curiously enough, the beliefs of the inhabitants require the time needed to pass each road to be equal either to a or b seconds. It's guaranteed that one can go between any pair of settlements by following a sequence of roads.

Codefortia was recently struck by the financial crisis. Therefore, the king decided to abandon some of the roads so that:

  * it will be possible to travel between each pair of cities using the remaining roads only, 
  * the sum of times required to pass each remaining road will be minimum possible (in other words, remaining roads must form minimum spanning tree, using the time to pass the road as its weight), 
  * among all the plans minimizing the sum of times above, the time required to travel between the king's residence (in settlement 1) and the parliament house (in settlement p) using the remaining roads only will be minimum possible. 



The king, however, forgot where the parliament house was. For each settlement p = 1, 2, ..., n, can you tell what is the minimum time required to travel between the king's residence and the parliament house (located in settlement p) after some roads are abandoned?

Input

The first line of the input contains four integers n, m, a and b (2 ≤ n ≤ 70, n - 1 ≤ m ≤ 200, 1 ≤ a < b ≤ 10^7) — the number of settlements and gravel roads in Codefortia, and two possible travel times. Each of the following lines contains three integers u, v, c (1 ≤ u, v ≤ n, u ≠ v, c ∈ \\{a, b\}) denoting a single gravel road between the settlements u and v, which requires c minutes to travel.

You can assume that the road network is connected and has no loops or multiedges.

Output

Output a single line containing n integers. The p-th of them should denote the minimum possible time required to travel from 1 to p after the selected roads are abandoned. Note that for each p you can abandon a different set of roads.

Examples

Input


5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20


Output


0 25 60 40 20


Input


6 7 13 22
1 2 13
2 3 13
1 4 22
3 4 13
4 5 13
5 6 13
6 1 13


Output


0 13 26 39 26 13

Note

The minimum possible sum of times required to pass each road in the first example is 85 — exactly one of the roads with passing time 25 must be abandoned. Note that after one of these roads is abandoned, it's now impossible to travel between settlements 1 and 3 in time 50.
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;
 
public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
        
        public int read() {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
            
            int sgn = 1;
            
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
            
            return res * sgn;
        }
        
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
        
        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next() {
            return readString();
        }
        
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(),"Main",1<<27).start();
    } 
    void union(int i, int j) {
        i = findSet(i);
        j = findSet(j);

        if(i == j)
            return;

        par[i] = j;
        size[j] += size[i];
    }
    int findSet(int i) {
        if(par[i] == i)
            return i;

        par[i] = findSet(par[i]);
        return par[i];
    }

    int par[], size[];
    public void run() {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int a = sc.nextInt();
        int b = sc.nextInt();

        if(a > b) {
            int temp = a;
            a = b;
            b = temp;
        }

        ArrayList<Edge> adj[] = new ArrayList[n];
        for(int i = 0; i < n; ++i)
            adj[i] = new ArrayList<>();

        for(int i = 0; i < m; ++i) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            int weight = sc.nextInt();

            adj[u].add(new Edge(v, weight));
            adj[v].add(new Edge(u, weight));
        }

        par = new int[n];
        size = new int[n];
        for(int i = 0; i < n; ++i) {
            par[i] = i;
            size[i] = 1;
        }

        for(int i = 0; i < n; ++i) {
            for(Edge curP : adj[i]) {
                int j = curP.dest;
                if(curP.weight == a)
                    union(i, j);
            }
        }

        int bit[] = new int[n];
        Arrays.fill(bit, -1);
        int ptr = 0;
        for(int i = 0; i < n; ++i) {
            if(findSet(i) == i && size[i] >= 4) 
                bit[i] = ptr++;
        }

        int cost[][] = new int[n][1 << ptr];
        for(int i = 0; i < n; ++i)
            Arrays.fill(cost[i], Integer.MAX_VALUE);

        int vis[][] = new int[n][1 << ptr];

        int ans[] = new int[n];
        Arrays.fill(ans, Integer.MAX_VALUE);

        PriorityQueue<Tuple> queue = new PriorityQueue<>(new Comparator<Tuple>() {
            public int compare(Tuple t1, Tuple t2) {
                return t1.cost - t2.cost;
            }
        });

        int mask = 0;
        if(bit[par[0]] != -1)
            mask |= (1 << bit[par[0]]);

        queue.add(new Tuple(0, mask, 0));
        cost[0][mask] = 0;

        while(!queue.isEmpty()) {
            Tuple curT = queue.poll();

            int ind = curT.ind;
            mask = curT.mask;

            if(vis[ind][mask] == 1)
                continue;

            int ccost = cost[ind][mask];

            vis[ind][mask] = 1;
            ans[ind] = min(ans[ind], ccost);

            int oldComp = par[ind];

            for(Edge curE : adj[ind]) {
                int j = curE.dest;
                int weight = curE.weight;

                int newComp = par[j];

                if(newComp == oldComp) {
                    if(weight == b)
                        continue;

                    int ncost = ccost + weight;
                    if(ncost < cost[j][mask]) {
                        cost[j][mask] = ncost;
                        queue.add(new Tuple(j, mask, ncost));
                    }
                }
                else {
                    if(bit[newComp] != -1 && (mask >> bit[newComp] & 1) == 1)
                        continue;

                    int cmask = mask;
                    if(bit[newComp] != -1)
                        cmask |= (1 << bit[newComp]);

                    int ncost = ccost + weight;
                    if(ncost < cost[j][cmask]) {
                        cost[j][cmask] = ncost;
                        queue.add(new Tuple(j, cmask, ncost));
                    } 
                } 
            }
        }

        for(int i : ans)
            w.print(i + " ");        

        w.close();
    }
}
class Tuple {
    int mask, ind, cost;
    Tuple(int a, int b, int c) {
        ind = a;
        mask = b;
        cost = c;
    }
}
class Edge {
    int dest, weight;
    Edge(int a, int b) {
        dest = a;
        weight = b;
    } 
}