#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#include<climits>
std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");
const int NMAX=50005;
const int INF=INT_MAX;
int n, m;
std::vector<std::pair<int, int>>G[NMAX];//val and node
std::vector<int>ans(NMAX, INF);
std::bitset<NMAX>f;
struct compare{
    bool operator()(const std::pair<int, int>&p1, const std::pair<int, int>&p2)
    {
        return p1.first>p2.first;
    }
};
void read()
{
    fin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int from, to, cost;
        fin>>from>>to>>cost;
        G[from].emplace_back(cost, to);
    }
}
void dijkstra()
{
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, compare>s;//cost and vertex
    s.emplace(0, 1);
    while(!s.empty())
    {
        std::pair<int, int>front=s.top();
        s.pop();
        if(f[front.second])
            continue;
        f[front.second]=true;

        for(auto it:G[front.second])
        {
            int newCost=it.first+front.first;
            if(newCost<ans[it.second])
            {
                ans[it.second]=newCost;
                s.emplace(newCost, it.second);
            }
        }
    }
}
void displayAns()
{
    for(int i=2; i<=n; ++i)
    {
        if(ans[i]==INT_MAX)
            ans[i]=0;
        fout<<ans[i]<<' ';
    }
}
int main()
{
    read();
    dijkstra();
    displayAns();
    return 0;
}