We claim that the answer is 3. If we reduce each of the numbers assigned on the roads by 1, then the priority of each city is reduced by $ n-1$, so all city still have distinct priorities. Now, each road is assigned an integer from $ \{0,1,2,\ldots,m-1\}$. If $ m-1=0$, all roads have the same priority. If $ m-1=1$, each road is assigned either 0 or 1. The greatest possible priority of a city is $ n-1$ and the smallest possible priority is $ 0$. So the priorities must be $ 0,1,2,\ldots,n-1$. All roads from the city of priority $ 0$ must be assigned 0, while all roads from the city of priority $ n-1$ must be assigned $ 1$. Considering the road connecting these two cities, we get a contradiction. Thus $ m-1\ge2$. We prove that $ m-1=2$ is possible. We will find an algorithm to assign each road an integer from $ \{1,2,3\}$. We divide into two cases: (i) $ n$ is even ($ n=2k$) Let the cities be $ C_1,C_2,\ldots,C_n$ such that the priority of $ C_i$ is less than that of $ C_j$ for all $ i<j$. We assign the roads from $ C_1,C_2,C_3,\ldots,C_n$ consecutively as follows: (see figure 1) The value of $ X$ is clearly greater than $ 2k-4$. In each assignment, the priority of each city does not increase by more than 2. (ii) $ n$ is odd ($ n=2k+1$) Similar to case (i), only different table (see figure 2).

Attachments:

easier solution: first consider 3 points or country its easy to prove that m>=3 becouse if m<=2 thus there are at least tow road that has a same number and ... now we prove by apriori that if m=3 its possible to put number on roads suppose that for n=k it is possible now consider another country with n roads put the smallest priority of n city in priority of new city and suppose that its k(k>n). now k=x1+x2+...+xn(x i=1,2,3)and the biggest number of road connect to city which has a biggest priority and ....if k=n-1 so we cant write k=x1+...+xn .now consider k=3n.it will be possible.if its not tru help me

Obviously for $m=2$ our priority can have just $n-1$ different value we have $n$ vertices => contradiction Now we prove $m=3$ is our suitable solution. for this we should just build this graph for any $n$. obvious claim : about each graph at least one of the states is true: state 1: the minimum of priorities isn't equal to $n-1$ state 2: the maximum of priorities isn't equal to $3(n-1)$ proof: if about one graph none of the states is true so the priority of one of the vertex for example $A$ is $n-1$ and the priority of $B$ is $3(n-1)$ so all of the contact edges of $A$ are $1$ and all of the edges of $B$ are $3$. Consider the edge between $A$ and $B$=>contradiction Now just we should use induction. Our conditions are true for $n=3,4,...,k-1$ We want to prove for $n=k$ so cosider the graph when $n=k-1$ . if the state 1 is true for this graph we just add one vertex in this graph and put the number of the edges between this new vertex and the others $1$ if the state 2 is true for this graph add one vertex and put new edges $n-1$ So we are done