#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define N 50003
#define oo 2000000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

bitset<N> f;
vector<pair<int,int> > g[N];
int n,m;
int dist[N];

priority_queue<pair<int,int> > q; //-cost,nod;

int x,y,c;

void Dijkstra(int nod)
{
    q.push(make_pair(0,nod));
    f[nod] = 1;
    for(int i=1; i<=n; ++i)
        dist[i] = oo;
    dist[nod] = 0;

    int cost,noda;
    int costurm,nodurm;

    while(!q.empty())
    {
        cost = -q.top().first;
        noda = q.top().second;
        q.pop();
        for(int i=0; i < g[noda].size(); ++i)
        {
            costurm = g[noda][i].second;
            nodurm = g[noda][i].first;

            if(!f[nodurm])
            {
                f[nodurm] = 1;
                if(dist[nodurm] > dist[noda] + costurm)
                {
                    dist[nodurm] = dist[noda] + costurm;
                    q.push(make_pair(-dist[nodurm],nodurm));
                }
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c)); //nod,cost
    }

    Dijkstra(1);

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

    return 0;
}