#include <bits/stdc++.h>
#define inf 169696969
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,dp[50005];
vector <pair<int,int> > lista[50005];
struct compare{
    bool operator () (int d1,int d2)
    {
        return dp[d1]>dp[d2];
    }
};
priority_queue<int,vector<int>,compare> pq;
bool ap[50005];
void dijkstra()
{
    for(int i=2; i<=n; i++)
    {
        dp[i]=inf;
    }
    pq.push(1);
    ap[1]=1;
    while(!pq.empty())
    {
        int nod=pq.top();
        pq.pop();
        ap[nod]=0;
        for(auto x:lista[nod])
        {
            if(dp[x.first]>dp[nod]+x.second)
            {
                dp[x.first]=dp[nod]+x.second;
                if(!ap[x.first])
                {
                    ap[x.first]=1;
                    pq.push(x.first);
                }
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        if(dp[i]==inf)
            out << "0 ";
        else
            out << dp[i] << ' ';
    }
}
int main()
{
    in >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        lista[x].push_back({y,c});
    }
    dijkstra();
    return 0;
}