#include <fstream>
#include <climits>
#include <queue>
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int N=50005;
typedef pair<int, int> pii;
int n,m,viz[N];
long long dmin[N];
vector<pii>g[N];

auto cmp = [](pii a, pii b) { return a.first>b.first; };
priority_queue <pii,vector<pii>,decltype(cmp)> q(cmp);

void init()
{
    dmin[1]=0;
    for(int i=2;i<=n;i++)
        dmin[i]=LLONG_MAX;
}
void citire()
{
    cin>>n>>m;
    int x,y,c;
    for(int i=0; i<m; i++)
    {
        cin>>x>>y>>c;
        g[x].push_back({c,y});
    }
}
void dijkstra()
{
    q.push({0,1});
    while(!q.empty())
    {
        int topnod=q.top().second;
        viz[topnod]=1;
        q.pop();
        for(auto i:g[topnod])
        {
            if(viz[i.second]==0 && dmin[topnod]+i.first<dmin[i.second])
            {
                dmin[i.second]=dmin[topnod]+i.first;
                q.push({i.first,i.second});
            }
        }
    }
}
void afisare()
{
    for(int i=2;i<=n;i++)
        if(dmin[i]==LLONG_MAX)
           dmin[i]=0;
    for(int i=2;i<=n;i++)
        cout<<dmin[i]<<' ';
}
int main()
{

    citire();
    init();
    dijkstra();
    afisare();
    return 0;
}