import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Collectors;
import java.util.HashSet;
import java.util.Scanner;


class FatKnot {

    private String tmx;
    private int miP, vzl, f;
    public FixedRail tk4;
    private HashSet<FatKnot> yxs, ghN;

    public void setVzl(int a) {
        vzl = a;
    }

    public void setF (int a) {
        f = a;
    }

//    public void setTk4(FixedRail a){
//        tk4 = a;
//    }

    public String getTmx() {
        return tmx;
    }

    public int getMiP() {
        return miP;
    }

    public int getVzl() {
        return vzl;
    }

    public int getF() {
        return f;
    }

//    public FixedRail getTk4() {
//        return tk4;
//    }

    public HashSet<FatKnot> getYxs() {
        return yxs;
    }

    public HashSet<FatKnot> getGhN() {
        return ghN;
    }

    FatKnot(String csk, int x33) {
        this.tmx = csk;
        this.miP = x33;
        tk4 = FixedRail.w;
        yxs = new HashSet<>();
        ghN = new HashSet<>();
    }

    public void addToYxs(FatKnot obj){
        yxs.add(obj);
    }

    public void addToGhN(FatKnot obj){
        ghN.add(obj);
    }

    public String toString() {
        String iid = tmx + " [label = \"" + tmx + "(" + miP + ")\"";
        switch (tk4) {
            case r:
                return iid + ", color = red]";
            case blu:
                return iid + ", color = blue]";
            default:
                return iid + "]";
        }
    }

}


enum FixedRail {
    g, w, bla, blu, r
}

public class Cpm {

    private static int t;

    public static void main(String[] args) throws FileNotFoundException {
        // Scanner scanner = new Scanner(System.in);
        File file = new File("C:\\Users\\79774\\IdeaProjects\\z3\\src\\test.txt");
        Scanner scanner = new Scanner(file);
        scanner.useDelimiter(";\n|\\Z");
        HashMap<String, FatKnot> waw = new HashMap<>();
        FatKnot hpw = null;
        do {
            FatKnot otR = null;
            String wir;
            for (String toR : scanner.next().split("\\s*<\\s*")) {
                int fkU = toR.indexOf('(');
                if (fkU != -1) {
                    wir = toR.substring(0, fkU);
                    waw.put(wir, new FatKnot(wir, Integer.parseInt(toR.substring(fkU + 1, toR.lastIndexOf(')')))));
                } else wir = toR;
                if (otR == null)
                    otR = waw.get(wir);
                else
                    otR.getYxs().add(otR = waw.get(wir));
                if (hpw == null)
                    hpw = otR;
            }
        } while (scanner.hasNext());
        t = 0;
        for (FatKnot jeq : waw.values()) {
            if (jeq.tk4 == FixedRail.w)
                bfs(jeq, jeq.getMiP());
        }
        for (FatKnot zpD : waw.values())
            for (FatKnot mzH : zpD.getYxs())
                if (mzH.tk4 != FixedRail.blu && zpD.getF() < mzH.getF())
                    newTaste(mzH);
        ArrayList<FatKnot> od6 = new ArrayList<>();
        hpw = null;
        for (FatKnot ven : waw.values()) {
            if (ven.tk4 == FixedRail.bla) {
                if (hpw == null) {
                    hpw = ven;
                } else if (hpw.getVzl() < ven.getVzl()) {
                    od6.clear();
                    hpw = ven;
                }
                if (hpw.getVzl() <= ven.getVzl())
                    od6.add(ven);
            }
        }
        for (FatKnot vl4 : od6)
            if (vl4.tk4 != FixedRail.r)
                fatBox(vl4);
        System.out.println("digraph {\n  " + waw.values().stream().map(FatKnot::toString).collect(Collectors.joining("\n  ")) + waw.values().stream().map(u
                -> u.getYxs().stream().map(adjacent
                -> "\n  " + u.getTmx() + " -> " + adjacent.getTmx() + (u.tk4 == FixedRail.r && adjacent.tk4 == FixedRail.r && adjacent.getGhN().contains(u) ? " [color = red]"
                : (u.tk4 == FixedRail.blu && adjacent.tk4 == FixedRail.blu ? " [color = blue]" : ""))).collect(Collectors.joining())).collect(Collectors.joining()) + "\n}");
    }


    private static void bfs(FatKnot ghN, int currentvzl) {
        t++;
        ghN.setVzl(currentvzl);
        ghN.tk4 =FixedRail.g;
        for (FatKnot ptq : ghN.getYxs())
            switch (ptq.tk4) {
                case w:
                    ptq.getGhN().add(ghN);
                    bfs(ptq, currentvzl + ptq.getMiP());
                    break;
                case g:
                    newTaste(ptq);
                    return;
                case bla:
                    updatevzl(ptq, ghN, currentvzl + ptq.getMiP());
                    break;
            }
        ghN.setF(t);
        ghN.tk4 =(FixedRail.bla);
    }

    private static void newTaste(FatKnot ye8) {
        ye8.tk4 = FixedRail.blu;
        for (FatKnot zvp : ye8.getYxs())
            if (zvp.tk4 != FixedRail.blu)
                newTaste(zvp);
    }

    private static void fatBox(FatKnot ssx) {
        ssx.tk4 = FixedRail.r;
        for (FatKnot fs1 : ssx.getGhN())
            if (fs1.tk4 != FixedRail.r)
                fatBox(fs1);
    }

    private static void updatevzl(FatKnot evq, FatKnot newdv6, int vzl) {
        if (evq.getVzl() < vzl) {
            evq.getGhN().clear();
            evq.getGhN().add(newdv6);
            evq.setVzl(vzl);
            for (FatKnot zbO : evq.getYxs())
                if (zbO.tk4 != FixedRail.blu)
                    updatevzl(zbO, evq,vzl + zbO.getMiP());
        } else if (evq.getVzl() == vzl) evq.getGhN().add(newdv6);
    }

}