#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector< pair<int ,int > > listavecini[100005];
const int oo=100000;
int n,m,i,verificare[100005],dist[100005];
struct compara{
bool operator()(int a,int b)
{
    return dist[a]>dist[b];
}
};
priority_queue<int ,vector<int>,compara>q;
void dijkstra(int nod)
{for(int i=1;i<=n;i++)
dist[i]=oo;
    dist[nod]=0;
verificare[nod]=1;
q.push(nod);
while(!q.empty())
{
    int actual=q.top();
    q.pop();
    verificare[actual]=0;
    for(unsigned int i=0;i<listavecini[actual].size();i++)
    {
        int vecin=listavecini[actual][i].first;
        int cost=listavecini[actual][i].second;
        if(dist[actual]+cost<dist[vecin])
        {
            dist[vecin]=dist[actual]+cost;
            if(!verificare[vecin])
            {
                q.push(vecin);
                verificare[vecin]=1;
            }
        }
    }

}

}
int main()
{f>>n>>m;
for(i=1;i<=m;i++)
{
    int x,y,c;
    f>>x>>y>>c;
    listavecini[x].push_back(make_pair(y,c));
}
dijkstra(1);
for(i=2;i<=n;i++)
    if(dist[i]!=oo)g<<dist[i]<<" ";
else g<<"-1 ";

    return 0;
}