The spread of rumors through social media and online social networks can not only disrupt the daily lives of citizens but also result in loss of life and property. A rumor spreads when individuals, who are unable decide the authenticity of the information, mistake the rumor as genuine information and pass it on to their acquaintances. We propose a solution where a set of individuals (based on their degree) in the social network are trained and provided resources to help them distinguish a rumor from genuine information. By formulating an optimization problem we calculate the optimum set of individuals, who must undergo training, and the quality of training that minimizes the expected training cost and ensures an upper bound on the size of the rumor outbreak. Our primary contribution is that although the optimization problem turns out to be non convex, we show that the problem is equivalent to solving a set of linear programs. This result also allows us to solve the problem of minimizing the size of rumor outbreak for a given cost budget. The optimum solution displays an interesting pattern which can be implemented as a heuristic. These results can prove to be very useful for social planners and law enforcement agencies for preventing dangerous rumors and misinformation epidemics.