#include <bits/stdc++.h>
#define NMAX 50500
#define MOD 2e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct poz{
    int first,second;
    bool operator <(poz b) const{
        return first>b.first;
    }
};

int dist[NMAX];
int n,m,x,y,c,use[NMAX];
vector<pair<long long,int>> v[NMAX];
priority_queue<pair<long long,int>>q;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        v[x].push_back({c,y});
    }

    dist[1]=0;
    for(int i=2;i<=n;++i)
        dist[i]=MOD;

    q.push({0,1});

    while(q.empty()==false)
    {
        x=q.top().second;
        q.pop();
        use[x]=1;

        for(auto i:v[x])
        {
            if(dist[i.second]>dist[x]+i.first)
                dist[i.second]=dist[x]+i.first;
            if(use[i.second]==0)
                q.push({dist[i.second],i.second});
        }
    }

    for(int i=2;i<=n;++i)
        if(dist[i]==MOD)
            fout<<"0 ";
        else
            fout<<dist[i]<<" ";

    return 0;
}