#include <bits/stdc++.h>
#define Nmax 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
list < pair <int,int> > G[Nmax];
int d[Nmax];
bitset <Nmax> inq;
class cmp
{
public:
    bool operator () (const int &x, const int &y)
    {
        return d[x]<d[y];
    }
};
priority_queue <int, vector <int>, cmp> pq;
int n,m;
void Dijkstra()
{
    int x;
    fill(d+2,d+n+1,INT_MAX);
    pq.push(1);
    while(!pq.empty())
    {
        x=pq.top();
        pq.pop();
        inq[x]=false;
        for(const auto &it:G[x])
            if(d[it.first]>d[x]+it.second)
            {
                d[it.first]=d[x]+it.second;
                if(!inq[it.first])
                {
                    inq[it.first]=true;
                    pq.push(it.first);
                }
            }
    }
}
int main()
{
    int i,j,k;
    f>>n>>m;
    while(m--)
    {
        f>>i>>j>>k;
        G[i].push_back({j,k});
    }
    Dijkstra();
    for(i=2;i<=n;i++)
        g<<((d[i]==INT_MAX)?0:d[i])<<' ';

    return 0;
}