#include <fstream>
#include <algorithm>
#include <queue>
#define s second
#define f first
#define X 1e9
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int a,b,c,n,m,i,Sol[50005];
priority_queue < pair<int,int> , vector< pair<int,int> >, greater< pair<int,int> > > Q;
vector < pair<int,int> > M[50005];
pair <int,int> ceva,P;
vector < pair<int,int> > :: iterator it;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        M[a].push_back({b,c});
    }
    for(i=1;i<=n;++i) Sol[i]=X;
    Q.push({0,1});
    while(!Q.empty())
    {
        ceva=Q.top();
        Q.pop();
        if(Sol[ceva.s]!=X) continue;
        Sol[ceva.s]=ceva.f;
        for(it=M[ceva.s].begin();it!=M[ceva.s].end();++it)
        {
            P=*it;
            Q.push({P.s+ceva.f,P.f});
        }
    }
    for(i=2;i<=n;++i) g<<(Sol[i]==X?0:Sol[i])<<" ";
    return 0;
}