#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,x,y,c,i,j,a,b;
long long int d[50005],viz[50005];
vector< pair<int, int>> v[50005];
class comp
{
public:
    bool operator()(long long int st, long long int dr)
    {
        return d[st]>d[dr];
    }
};
priority_queue<int, vector<int>, comp> q;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    q.push(1);
    while(!q.empty())
    {
        a=q.top();
        q.pop();
        if(viz[a]==0)
        {
            viz[a]=1;
            for(i=0;i<v[a].size();i++)
            {
                b=v[a][i].first;
                if(d[b]>d[a]+v[a][i].second)
                {
                    d[b]=d[a]+v[a][i].second;
                    q.push(b);
                }
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]!=inf)
            fout<<d[i];
        else
            fout<<0;
        fout<<" ";
    }
    return 0;
}