Last year, 378 insurgency-related deaths were recorded in Dagestan, compared with 134 in Ingushetia and 127 in Chechnya
Two armed men in camouflage holding Kalashnikov rifles enter the shop and tell the customers to leave. The terrified cashier stumbles past as one of the men puts a bomb on the counter and sets the timer.
He does not bother emptying the till, he just walks out of the door.
Seconds later, the shop is filled with smoke.
Attacks like this one caught on supermarket security cameras - in which Islamic fighters punish shops that sell alcohol - have become routine events in Dagestan's capital, Makhachkala.
The owners typically get a warning first, often delivered by text message, or on a USB memory stick thrown through car windows, or into a letterbox.If they ignore it, there may be a bomb or a shootout or the owners may agree to pay protection money.
"The fighters like to portray themselves as so devout," says a lieutenant colonel in the anti-terrorism police, who I will call Bashir.
"But many are just cynical criminals running protection rackets."
I met Bashir at a football match, watching the Cameroonian striker Samuel Eto'o - reportedly the world's best-paid footballer - play for Anzhi Makhachkala.
The atmosphere inside the stadium was relaxed, even joyful, with old men munching sunflower seeds and children waving flags, despite the heavy security outside.
After the game, a smiling Eto'o told me he was proud to play in Dagestan - but he does not spend much time here, heading straight back to the safety of Moscow after every match.
In the centre of Makhachkala, there are armed police on almost every corner.
Bashir drives me past a place where two car bombs recently killed a policeman and a young girl and wounded 60 police and passers-by.
"When our guys rushed to the scene of the first explosion, a blast about 12 times more powerful went off," he adds."It was a trap. They wanted to get as many of us as possible."
He asks me not to use his real name, or to photograph his face. Government officials and policemen are the main targets of the increasingly ruthless Islamic insurgents.
Many officers are too scared to go on to the street in their uniform. Police who have to stop and search cars often wear masks.
But unlike some of his colleagues, Bashir seems to want to understand why so many young Dagestanis have joined the rebels and gone into hiding - known here as "going into the forest".
At the university, I watch him lecture students about the dangers of fundamentalist websites. He tells them a cautionary tale about a young medical student who made some so-called friends online, and who later forced him to plant a car bomb.
Bashir is joined by an imam, who urges moderation and compliance with Russian law. "If a man only gets secular education he will be heartless - if he only gets religious education he'll be a fanatic," the imam says.
Most Muslims in Dagestan are Sufi but younger people are increasingly drawn to the Salafi branch of Islam, which is less mystical, more puritanical and, crucially, outside the control of the state.
This is seen by the interior ministry as a problem, as I discover in the village of Sovietskoye, three hours south of Makhachkala.
Said Gereikhanov, the young imam at the village mosque, tells me about a day last May, when dozens of Salafi mosque-goers were detained and beaten by police.
Plain-clothed security officers burst into the mosque in muddy boots, during Friday prayers, and told everyone to leave, he says. Outside, they found themselves surrounded by masked men with guns, and the whole congregation of 150 people, including 15 school boys, was taken to a police station in a neighbouring town.Police then summoned the headmaster of the village secondary school, Sadikullah Akhmedov. Said says he was shocked by the brutal treatment of the teenagers - and by Mr Akhmedov's failure to intercede on their behalf.
He shows me photographs of bruised bodies and young men with half of their beards shaved off.
On the night of 9 July, two months after the arrests at the mosque, there was a more serious incident - one which sent shock waves through Russia. Mr Akhmedov was gunned down in his own sitting room by unknown assailants.
At the school nobody is keen to talk about it. The headmaster's distraught widow, Djeramat, tells me she has no idea why her husband was killed.
But Said, the imam, says Mr Akhmedov banned the hijab in school and treated girls wearing them as if they "were armed with weapons".
Said believes only the radical fighters could be responsible. He adds wearily: "You can't deliver justice through murders. They just make things worse. This war has already been going on for 20 years."
Like Bashir, Rizvan Kurbanov, Dagestan's deputy premier and the man in charge of police and security, is keen to reach out to disaffected youth.
Clutching his iPad, Mr Kurbanov shows me his Facebook account. He says when more than 20 terrorist internet sites are putting pressure on Dagestan, the government has to reclaim cyberspace and use social networks to stop young people from being seduced by online jihadists.
President Medvedev visited Dagestan in 2009, days after a sniper killed the republic's interior minister
"No place on earth is safe from terrorism. Today the Caucasus, Dagestan included, is of heightened interest to terrorist organisations and they try to spread unrest here," he says.
An energetic man with a mop of grey hair, he chairs a new commission to persuade fighters to lay down their arms and go back to their families."The commission is like a bridge between a person who's lost his way, who's been duped and is in the woods, and society. He can walk across this bridge, say I've done this and that, please forgive me."
This feels like a new approach in the North Caucasus where strong-hand tactics and repression have long been the rule, with the full backing of the Kremlin.
In neighbouring Chechnya, forces loyal to President Ramzan Kadyrov have been accused of burning down the houses of suspected militants, leaving their families homeless.
Mr Kurbanov, on the other hand, urges parents to track down wayward sons and bring them round a table where they can appeal for clemency.
So far though the commission has only dealt with minor figures in the insurgency and government's leniency only goes so far, Mr Kurbanov says.
"Those who don't understand, the ones I call non-people - because like animals they just crave blood and want to fight - they will be dealt with briefly by the necessary power agencies."
the most dangerous place in Europe