#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
const int nmax=5e4, inf=2e9;
int n, m;
int dst[nmax+5], viz[nmax+5];
vector <pair <int, int> > G[nmax+5];
priority_queue <pair <int, int> > pq;

void dijkstra(void)
{
    int nod, nods, cost;
    pq.push({0, 1});
    for(int i=2; i<=n; i++)
        dst[i]=inf;
    while(!pq.empty())
    {
        nod=pq.top().second;
        pq.pop();
        if(viz[nod])
            continue;
        viz[nod]=1;
        for(auto vec:G[nod])
        {
            nods=vec.second;
            cost=vec.first;
            if(dst[nods]>dst[nod]+cost)
            {
                dst[nods]=dst[nod]+cost;
                pq.push({-cost, nods});
            }
        }
    }
}

int main()
{
    fi>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        fi>>x>>y>>c;
        G[x].push_back({c, y});
    }
    dijkstra();
    for(int i=2; i<=n; i++)
        if(dst[i]==inf)
            fo<<0<<" ";
        else
            fo<<dst[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}