#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <stack>
#define nmax 50005
using namespace std;
int d[nmax],tata[nmax];
bool viz[nmax];
class nod
{
    public:
    int x,cost;
};
class prio
{
    public:
    bool operator() (const nod &A, const nod &B)
    {
        return A.cost>B.cost;
    }
};
vector <nod> a[nmax];
priority_queue <nod,vector<nod>,prio> q;
void solve()
{
    int x,y,cost,i;
    nod u,v;
    while (!q.empty())
    {
        u=q.top();
        q.pop();
        if (!viz[u.x])
        {
            viz[u.x]=true;
            x=u.x;
            for (i=0;i<a[x].size();i++)
            {
                y=a[x][i].x;
                cost=a[x][i].cost;
                if (d[y]>d[x]+cost)
                {
                    d[y]=d[x]+cost;
                    tata[y]=x;
                    v.x=y;
                    v.cost=d[i];
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n,m,i,x;
    nod u;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>u.x>>u.cost;
        a[x].push_back(u);
    }
    for (i=2;i<=n;i++)
        d[i]=INT_MAX;
    u.x=1;
    u.cost=0;
    q.push(u);
    solve();
    for (i=2;i<=n;i++)
    {
        if (d[i]==INT_MAX)
            d[i]=0;
        fout<<d[i]<<' ';
    }
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}